学步园

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

题意：有n头牛比赛，m种比赛结果，最后问你一共有多少头牛的排名被确定了，其中如果a战胜b，b战胜c，则也可以说a战胜c，即可以传递胜负。求能确定排名的牛的数目。

思路：Floyd算法变形，关于传递闭包网上没有搜到能看懂的资料……不过大致可以理解是什么意思。感觉思路很巧妙。

解法完全参照了：http://www.cnblogs.com/pushing-my-way/archive/2012/08/23/2652153.html

#include <cstdio>
#include <cstring>

bool map[105][105];
int n,m;

void Floyd ()
{
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			for (int k=1;k<=n;k++)
				map[j][k]=map[j][k] || map[j][i] && map[i][k];
}

int main ()
{
	while (~scanf("%d%d",&n,&m))
	{
		memset(map,false,sizeof(map));
		while (m--)
		{
			int u,v;
			scanf("%d%d",&u,&v);
            map[u][v]=true;
		}
		Floyd ();
		int ans=0,cnt=0;
		for (int i=1;i<=n;i++)
		{
			cnt=0;
			for (int j=1;j<=n;j++)
				if (i==j) continue;
				else if (map[i][j] || map[j][i])
					cnt++;
			if (cnt==n-1)  //出度+入度=n-1;
				ans++;
		}
		printf("%d\n",ans);
	}
	return 0;
}