poj 3660 Cow Contest 传递闭包

题目链接：

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

题目大意：

　　有n头牛，每头牛都有一个战斗值，农夫约翰想给这些牛排名次，但是只有m场比赛，约翰想知道有多少头牛的名次是确定的。

解题思路：

　　是一个求传递闭包的题目，传递性就是如果i可以到达k，k可以到达j，那么i就可以到达j，求传递闭包就是把图中所有满足这样的性质的节点全部求出来，我们可以知道任意两点是否向通。可以用floyd实现传递闭包。

经过分析可知，如果牛a与其他的牛都有关系（无论什么关系），那么牛a的名次就是确定的。

#include <vector>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 110

int map[maxn][maxn];
int n;

void init ();
void floyd ();

int main ()
{
    int m;
    while (scanf ("%d %d", &n, &m) != EOF)
    {
        init ();
        while (m --)
        {
            int a, b;
            scanf ("%d %d", &a, &b);
            map[a][b] = 1;
        }
        floyd ();
        for (int i=1; i<=n; i++)//统计与牛a有关的牛有几个
            for (int j=0; j<=n; j++)
                if (map[i][j])
                    map[0][i] ++, map[0][j] ++;


        int sum = 0;
        for (int i=1; i<=n; i++)
            if (map[0][i] == n - 1)
                sum ++;
        printf ("%d
", sum);
    }
    return 0;
}

void init ()
{
    int i, j;
    for (i=0; i<maxn; i++)
        for (j=0; j<maxn; j++)
            map[i][j] = 0;
}
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 (map[i][k] && map[k][j])//传递性
                    map[i][j] = 1;
}