POJ3660-Cow Contest

题目传送：poj3660
题目描述：

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

题目理解：有 n 头牛比赛，m 种比赛结果，问通过 m 种比赛结果判断有多少头牛的排名可以被确定。注意到若牛 a 和 c 没有直接的比赛结果，却有 a 胜于 b ，b 胜于 c ,那么其实 a 和 c 的比赛结果也是确定的。接下来分析如何判断牛的排名是否被确定：显然，如果有 w 头牛胜于 a ，a 胜于 l 头牛，若 w + l = n - 1 , (注意 n 是牛的数量) 那么 a 的排名已经确定。

抽象为floyd传递闭包算法，即每个顶点的出度+入度=顶点数-1,那么排名已确定。

floyd

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>//memset函数头文件
using namespace std;
const int maxn=100+10;
int e[maxn][maxn];
int n,m;
void floyd(){
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                e[i][j]=e[i][j]||(e[i][k]&&e[k][j]);//i和j的胜负可以确定或者间接确定
            }
        }
    }
}
int main(){
    cin>>n>>m;
    int a,b;
    memset(e,0,sizeof(e));
    for(int i=1;i<=m;i++){
        cin>>a>>b;
        e[a][b]=1;
    }
    floyd();
    int ans=0;//ans是能确定排名的牛的数量
    for(int i=1;i<=n;i++){
        int sum=0;//sum是和i能确定关系的j的数量
        for(int j=1;j<=n;j++){
            if(i==j)continue;//跳过自己和自己
            else if(e[i][j]||e[j][i])//如果i和j关系确定
                sum++;
        }
        if(sum==n-1)ans++;
    }
    cout<<ans<<endl;
    return 0;
}