比赛

 第3题     比赛 查看测评数据信息

N 头奶牛，编号 1∼N，一起参加比赛。奶牛的战斗力两两不同。这些奶牛之间已经进行了 M 轮两两对决。在对决中，战斗力高的奶牛一定会战胜战斗力低的奶牛。请问，通过上述 M 轮对决的结果，可以确定多少头奶牛的具体战斗力排名。1≤N≤100 ，1≤M≤4500，数据保证合法。
输入格式

第一行包含两个整数 N,M。

接下来 M 行，每行包含两个整数 a,b，表示奶牛 a 和奶牛 b 之间进行了对决，并且奶牛 a 战胜了奶牛 b。

输出格式

输出可以确定具体战斗力排名的奶牛数量。

输入/输出例子1

输入：

5 5

4 3

4 2

3 2

1 2

2 5

输出：

2

样例解释

2 号奶牛输给了 1,3,4 号奶牛，战胜了 5 号奶牛，可以确定它的战斗力排名为 4。

5 号奶牛输给了排在第 4 的 2 号奶牛，所以它的战斗力排名为 5。

其它奶牛不确定。

第一个思路是，找点的入度出度（遍历），如果入度+出度-1（减去自己）==n，那就可以确定

#include <bits/stdc++.h>
using namespace std;

int n, m, t1, t2, vis[105], vis2[105], cnt=0, cnt2=0, ans=0;
vector<int>a[105], a1[105]; 
void dfs(int now)
{
	if (vis[now]==1) return ;
	vis[now]=1;
	cnt++;
	for (int i=0; i<a[now].size(); i++)
		dfs(a[now][i]);
}
void dfs2(int now)
{
	if (vis2[now]==1) return ;
	vis2[now]=1;
	cnt2++;
	for (int i=0; i<a1[now].size(); i++)
		dfs2(a1[now][i]);
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=m; i++)
	{
		scanf("%d%d", &t1, &t2);
		a[t1].push_back(t2);
		a1[t2].push_back(t1);
	}
	for (int i=1; i<=n; i++)
	{
		cnt=0, cnt2=0;
		memset(vis, 0, sizeof(vis));
		memset(vis2, 0, sizeof(vis2));
		dfs(i);
		dfs2(i);
		//printf("%d %d\n", cnt, cnt2);
		if (cnt+cnt2-1==n) ans++;	
	}
	printf("%d", ans);
	
	return 0;
} 

第二个思路是floyd，但是现在还没做出来