傳遞閉包的求法，POJ 3660 Cow Contest (閉包傳遞)

Cow Contest

Time Limit:?1000MS	?	Memory Limit:?65536K
Total Submissions:?7690	?	Accepted:?4288

Description

N?(1 ≤?N?≤ 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow?A?has a greater skill level than cow?B?(1 ≤?A?≤?N; 1 ≤?B?≤?N;?A?≠?B), then cow?A?will always beat cow?B.

Farmer John is trying to rank the cows by skill level. Given a list the results of?M?(1 ≤?M?≤ 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

Input

傳遞閉包的求法。* Line 1: Two space-separated integers:?N?and?M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer,?A, is the winner) of a single round of competition:?A?and?B

Output

* Line 1: A single integer representing the number of cows whose ranks can be determined
　

Sample Input

5 5
4 3
4 2
3 2
1 2
2 5

Sample Output

2




剛才學了下閉包傳遞，簡單來說就是用Floyd來求兩點是否連通。這題里，如果一點的入度加上出度等于N-1，那么就可確定這點的等級，因為除了它自己之外的所有節點要么在它之前要么在它之后，不管它前面的節點后后面的節點怎么排序，都不會影響到它。

#include <iostream>
#include <cstdio>
using    namespace    std;

const    int    SIZE = 105;
int    N,M;
int    IN[SIZE],OUT[SIZE];
bool    G[SIZE][SIZE];

int    main(void)
{
    int    from,to;
    int    ans;

    while(scanf("%d%d",&N,&M) != EOF)
    {
        fill(&G[0][0],&G[N][N],false);
        for(int i = 0;i <= N;i ++)
            IN[i] = OUT[i] = 0;

        for(int i = 0;i < M;i ++)
        {
            scanf("%d%d",&from,&to);
            G[from][to] = true;
        }

        for(int k = 1;k <= N;k ++)
            for(int i = 1;i <= N;i ++)
                for(int j = 1;j <= N;j ++)
                    G[i][j] = G[i][j] || G[i][k] && G[k][j];
        for(int i = 1;i <= N;i ++)
            for(int j = 1;j <= N;j ++)
                if(G[i][j])
                {
                    IN[j] ++;
                    OUT[i] ++;
                }

        ans = 0;        
        for(int i = 1;i <= N;i ++)
            if(IN[i] + OUT[i] == N - 1)
                ans ++;
        printf("%d\n",ans);
    }

    return    0;
}

?