POJ 3660 Cow Contest （Floyd）

http://poj.org/problem?id=3660

题目大意：n头牛两两比赛经过m场比赛后能判断名次的有几头可转

化为路径问题，用Floyd将能够到达的路径标记为1，如果一个点能

够到达剩余你n - 1个点则能判断该点的名次

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<queue>
#define INF 0x3f3f3f3f
#define max(a, b)(a > b ? a : b)
#define min(a, b)(a < b ? a : b)
#define N 110

int G[N][N];
int n;

void Floyd()
{
    int i, j, k;
    for(k = 1 ; k <= n ; k++)
    {
        for(i = 1 ; i <= n ; i++)
        {
            for(j = 1 ; j <= n ; j++)
            {
                if(G[i][k] == 1 && G[k][j] == 1)//如果i能到k，k能到j，则i一定能到j
                    G[i][j] = 1;
            }
        }
    }
}

int main()
{
    int m, i, j, a, b, t, ans;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        ans = 0;
        memset(G, 0, sizeof(G));
        for(i = 1 ; i <= m ; i++)
        {
            scanf("%d%d", &a, &b);
            G[a][b] = 1;
        }
        Floyd();
        for(i = 1 ; i <= n ; i++)
        {
            t = 0;
            for(j = 1 ; j <= n ; j++)
                t += G[i][j] + G[j][i];
            if(t == n - 1)
                ans++;
        }
        printf("%d
", ans);
    }
    return 0;
}