Cow Contest---poj3660

题目链接：http://poj.org/problem?id=3660

题意：有n头牛，m个关系，a b意思是a能打败b；求能确定排名的有几个；

如果一头牛被x头牛打败，并且可以打败y头牛，如果x+y=n-1，则我们容易知道这头牛的排名就被确定了，所以我们只要将任一头牛，可以打败其他的牛的个数x， 和能打败该牛的牛的个数y求出来，在遍历所有牛判断一下是否满足x+y=n-1，就知道这个牛的排名是否能确定了（而传递闭包，正好将所有能得出关系都求出来了）

传递闭包就是如果a>b,b>c那么a>c;

 #include<iostream>

 #include<stdio.h>

 #include<math.h>

 #include<string.h>

 #include<algorithm>

 #define INF 0xfffffff

 #define N 1100

 using namespace std;

 int n,m;

 int maps[N][N];

 void Floyd()

 {

     int i,j,k;

     for(k=;k<=n;k++)

         for(i=;i<=n;i++)

             for(j=;j<=n;j++)

                 if(maps[i][k]==&&maps[k][j]==)

                     maps[i][j]=;

 }

 int main()

 {

     int i,j,a,b;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         for(i=;i<=n;i++)

             for(j=;j<=n;j++)

                 maps[i][j]=;

         for(i=;i<m;i++)

         {

             scanf("%d%d",&a,&b);

             maps[a][b]=;

         }

         Floyd();

         int ans=;

         for(i=;i<=n;i++)

         {

             int k=;

             for(j=;j<=n;j++)

             {

                 if(i==j)continue;

                 if(maps[i][j]==||maps[j][i]==)

                     k++;

             }

             if(k==n-)

                 ans++;

         }

         printf("%d\n",ans);

     }

     return ;

 }