本文共 1018 字，大约阅读时间需要 3 分钟。

#include 
   
    #include 
    
     using namespace std;const int n_max = 100 + 5;const int m_max = 4500 + 5;int graph[n_max][n_max];int n, m;int a, b, cnt, ans;void Floyd(){    for(int k = 1; k <= n; k ++)        for(int i = 1; i <= n; i ++)            for(int j = 1; j <= n; j ++)                graph[i][j] = graph[i][j] || (graph[i][k] && graph[k][j]);}int main(){    while(~scanf("%d %d", & n, & m))    {        memset(graph, 0, sizeof(graph));        for(int i = 0; i < m; i ++)        {            scanf("%d %d", & a, & b);            graph[a][b] = 1;        }        Floyd();        ans = 0;        for(int i = 1; i <= n; i ++)        {            cnt = 0;            for(int j = 1; j <= n; j ++)                if(graph[i][j] || graph[j][i])                    cnt ++;            if(cnt == n - 1)                ans ++;        }        printf("%d\n", ans);    }}
    
   

：

有n头牛比赛，m种比赛结果，最后问你一共有多少头牛的排名被确定了，其中如果a战胜b，b战胜c，则也可以说a战胜c，即可以传递胜负。

题解：

用Floyd算法比较简单。就是求每个点与其他点是否连通。如果 入点的个数 加上 出点的个数 等于 n - 1，则说明这个点的排名已经确定。

转载地址：http://cjtpi.baihongyu.com/