BZOJ-1612: [Usaco2008 Jan]Cow Contest奶牛的比赛

Description

FJ的N(1 <= N <= 100)头奶牛们最近参加了场程序设计竞赛:)。在赛场上，奶牛们按1..N依次编号。每头奶牛的编程能力不尽相同，并且没有哪两头奶牛的水平不相上下，也就是说，奶牛们的编程能力有明确的排名。 整个比赛被分成了若干轮，每一轮是两头指定编号的奶牛的对决。如果编号为A的奶牛的编程能力强于编号为B的奶牛(1 <= A <= N; 1 <= B <= N; A != B) ，那么她们的对决中，编号为A的奶牛总是能胜出。 FJ想知道奶牛们编程能力的具体排名，于是他找来了奶牛们所有 M(1 <= M <= 4,500)轮比赛的结果，希望你能根据这些信息，推断出尽可能多的奶牛的编程能力排名。比赛结果保证不会自相矛盾。

如果某个点排名能够确定，当且仅当每个点能够到达该点或是能被该点到达。所以floyd一遍就好了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ans;
bool map[110][110];
int main()
{
    scanf("%d%d",&n,&m);
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        map[x][y]=1;
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(map[i][k]&&map[k][j]) map[i][j]=1;
    for(int i=1;i<=n;i++)
    {
        int tmp=0;
        for(int j=1;j<=n;j++)
            if(map[j][i]||map[i][j]) tmp++;
        if(tmp==n-1) ans++;
    }
    printf("%d",ans);
    return 0;
}