摘要
Title: 4244. 牛的比赛
Tag: floyd传递闭包
Memory Limit: 64 MB
Time Limit: 1000 ms

4244. 牛的比赛

题意

N 头奶牛，编号 1∼N，一起参加比赛。
奶牛的战斗力两两不同。
这些奶牛之间已经进行了 M 轮两两对决。
在对决中，战斗力高的奶牛一定会战胜战斗力低的奶牛。
请问，通过上述 M 轮对决的结果，可以确定多少头奶牛的具体战斗力排名。
思路

floyd传递闭包的板子题， $a$ 战胜 $b$ 就相当于 $a$ 连向 $b$ 了一条有向边

当某只奶牛确定了排名 相当于 该奶牛和其他 $n - 1$ 头奶牛确定的关系

代码

'''
Author: NEFU AB-IN
Date: 2022-02-12 15:03:48
FilePath: \ACM\Acwing\4244.py
LastEditTime: 2022-02-12 15:09:08
'''

N = 155
g = [[0 for _ in range(N)] for _ in range(N)]

if __name__ == "__main__":
    n, m = map(int, input().split())

    for i in range(1, n + 1):
        g[i][i] = 1
    for i in range(m):
        x, y = map(int, input().split())
        g[x][y] = 1

    for k in range(1, n + 1):
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if g[i][k] and g[k][j]:
                    g[i][j] = 1

    res = 0
    for i in range(1, n + 1):
        cnt = 0
        for j in range(1, n + 1):
            if g[i][j] or g[j][i]:
                cnt += 1
        if cnt == n:
            res += 1

    print(res)

4244. 牛的比赛

题意

思路

代码