2009-2-25pku3660.txt

数据结构中的单元最短路径算法的题目和源代码！其中所有的题目都能在PKU上找的到！

/*
题目：n头牛进行m场比赛，问能确定排名的有多少头牛。

解答：构造一个n个点的有向图，如果牛a胜b，那么a->b，如果a->b，b->c，则有a->c，这个用floyd。
最后得到该图的传递闭包link的二维数组。最后统计每一个点入度和出度和为n-1的点的个数即可。
*/
#include<stdio.h>
#include<string.h>
const int MAX=105;
/*
有向图的传递闭包！
注意传递之前一定要初始化！
如果i!=j&&(i,j)不属于E(边的集合)  t[i][j]=0;
如果i=j||(i,j)属于E(边的集合)     t[i][j]=1;
*/
void Transitive_Closure(int n,bool t[][MAX])
{
	int i,j,k;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				t[i][j]=t[i][j]|(t[i][k]&t[k][j]);
}
int main()
{
	int n,i,j,m,st,ed,sum,num;
	bool t[MAX][MAX];
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		memset(t,false,sizeof(t));
		for(i=1;i<=n;i++)
			t[i][i]=true;
		for(i=1;i<=m;i++)
		{
			scanf("%d%d",&st,&ed);
			t[st][ed]=true;
		}//上面的代码都是初始化
		Transitive_Closure(n,t);
		sum=0;
		for(i=1;i<=n;i++)
		{
		   num=0;
		   for(j=1;j<=n;j++)
			  if(i==j)
				  continue;
			  else
				  num+=(t[i][j]||t[j][i]);//统计出度和入度的个数!
			sum+=(num==n-1);
		}
		printf("%d\n",sum);
	}
		return 0;
}
/*
5 5
4 3
4 2
3 2
1 2
2 5

2
*/