比赛 防止浮躁的小练习v0.7 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 kxxy 运行时间 1.715 s
代码语言 C++ 内存使用 2.99 MiB
提交时间 2016-10-27 16:09:21
显示代码纯文本
//草<->1 兔<->2 狐<->3 鼠<->4 猫头鹰<->5
//吃虫的鸟<->6 蜘蛛<->7 蛇<->8 青蛙<->9 食草昆虫<->10.
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxx=100010;
int in[maxx],out[maxx];
long long cnt[maxx];
vector<int>v[maxx];
queue<int>q;
int n,m,a,b;
int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		v[i].clear();
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		v[a].push_back(b);
		in[b]++;
		out[a]++;
	}
	long long ans=0;
	for(int i=1;i<=n;i++)
		if(!in[i])
		{
			cnt[i]=1;
			q.push(i);
			if(!out[i])
				ans--;
		}
	while(!q.empty())
	{
		int c=q.front();
		q.pop();
		for(int i=0;i<v[c].size();i++)
		{
			cnt[v[c][i]]+=cnt[c];
			in[v[c][i]]--;
			if(!in[v[c][i]])
				q.push(v[c][i]);
		}
	}
	for(int i=1;i<=n;i++)
		if(!out[i])
			ans+=cnt[i];
	cout<<ans<<endl;
	return 0;
}