比赛 至少完成十道练习 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 swttc 运行时间 0.270 s
代码语言 C++ 内存使用 3.37 MiB
提交时间 2017-05-22 22:55:18
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>

using namespace std;

int n,m,inde[100010],oude[100010],ans[100010],inq[100010],anss,indee[100010];
queue<int>qu;
vector<int>e[100010];

void work()
{
	for(int i=1;i<=n;i++)
	{
		if(inde[i]==0&&oude[i]!=0)
		{
			qu.push(i);
			inq[i]=ans[i]=1;
		}
	}
	while(!qu.empty())
	{
		int u=qu.front();
		qu.pop();
		inq[u]=0;
		for(int i=0;i<e[u].size();i++)
		{
			ans[e[u][i]]+=ans[u];
			inde[e[u][i]]--; 
			if(inq[e[u][i]]==0&&inde[e[u][i]]==0)
			{
				qu.push(e[u][i]);
				inq[e[u][i]]=1;
			}
		}
	}
	return;
}

int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		e[a].push_back(b);
		inde[b]++;
		indee[b]++;
		oude[a]++;
	}
	work();
	for(int i=1;i<=n;i++)
	{
		if(oude[i]==0&&indee[i]!=0)
		{
			anss+=ans[i];
		}
	}
	printf("%d",anss);
	return 0;
}