比赛 EYOI与SBOI开学欢乐赛9th 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 康尚诚 运行时间 0.473 s
代码语言 C++ 内存使用 5.27 MiB
提交时间 2022-09-30 20:48:27
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=200010;
struct node
{
	int to;
	int pre;
}edge[M];
int lst[N],cnt=0;
int rudu[N],chudu[N];
int f[N];//每个点后能分成的食物链数
void addedge(int from,int to)
{
	cnt++;
	edge[cnt].to=to;
	edge[cnt].pre=lst[from];
	lst[from]=cnt;
	rudu[to]++;
	chudu[from]++;
}
int dfs(int now)
{
	if(chudu[now]==0)
	{
		f[now]=1;
		return 1;
	}
	if(f[now])
	{
		return f[now];
	}
	for(int i=lst[now];i!=0;i=edge[i].pre)
	{
		int to=edge[i].to;
		f[now]+=dfs(to);
	}
	return f[now];
}
int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	int n,m;//物种数和关系数
	cin>>n>>m;
	int a,b;
	for(int i=1;i<=m;i++)
	{
		cin>>a>>b;
		addedge(a,b);
	}
	int num=0;
	for(int i=1;i<=n;i++)
	{
		if(rudu[i]==0&&chudu[i]!=0)
		{
//			cout<<i<<"";
			num+=dfs(i);
		}
	}
	cout<<num;
}