题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1612
题意:
有n头牛比赛。
告诉你m组(a,b),表示牛a成绩比牛b高。
保证排名没有并列。
问你有多少只牛的排名已经确定。
题解:
对于一头牛,它的排名确定的条件是:它前面的牛数量 + 它后面的牛数量 = n-1
所以对于(a,b),连一条有向边a->b。
然后做floyd传递闭包。
枚举每一头牛,统计与它连通的牛的个数sum。
如果sum = n-1,则ans++。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 105 using namespace std; int n,m;
int ans=;
bool dis[MAX_N][MAX_N]; int main()
{
cin>>n>>m;
memset(dis,false,sizeof(dis));
int a,b;
for(int i=;i<m;i++)
{
cin>>a>>b;
dis[a][b]=true;
}
for(int k=;k<=n;k++)
{
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(i!=j && j!=k && i!=k)
{
dis[i][j]|=(dis[i][k]&dis[k][j]);
}
}
}
}
for(int i=;i<=n;i++)
{
int sum=;
for(int j=;j<=n;j++)
{
sum+=(dis[i][j]|dis[j][i]);
}
if(sum==n-) ans++;
}
cout<<ans<<endl;
}