传送门：http://poj.org/problem?id=3660
题意：有n头牛， 给你m对关系。（a, b）表示牛a能打败牛b， 求在给出的这些关系下， 能确定多少头牛的排名。
传递闭包： 关系之间具有传递性（例如a> b, b> c, 那么a> c）， 在那些已给出的关系基础上， 通过传递性， 把所有可能的关系都找出来。
思路：假设一头牛可以被X头牛打败，可以打败Y头牛。如果这头牛的排名可以确定则X+Y=N-1。想到Floyd正好可以求X→Y的关系，只是将Floyd求距离改成了判断两者之间是否直接联通或者间接联通。
代码:
#include<iostream>
#include<cstdio>
using namespace std;
const int maxn = 202;
int w[maxn][maxn];
void floyd(int n)
{
for(int k = 1; k <= n; k++)
{
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(w[i][j] || (w[i][k] && w[k][j]))//直接联通或者间接联通
{
w[i][j] = 1;
}
}
}
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
w[i][j] = 0;
}
}
for(int i = 1; i <= m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
w[a][b] = 1;//两者之间有关系 则赋值为1
}
floyd(n);
int ans = 0;
for(int i = 1; i <= n; i++)
{
int sum = 0;
for(int j = 1; j <= n; j++)
{
if(i == j)
continue;
else if(w[i][j] || w[j][i])//记录能打败J的和被J打败的个数
sum++;
}
if(sum == n - 1)
ans++;
}
cout << ans << endl;
}