比赛 防止浮躁的小练习v0.7 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 NVIDIA 运行时间 0.299 s
代码语言 C++ 内存使用 9.64 MiB
提交时间 2016-10-27 17:46:13
显示代码纯文本
#include<cstdio>
#include<cstring>
using namespace std;
bool chudu[100100]={0};
bool rudu[100100]={0};
int sumt[100100]={0};
int head[500100]={0};
int ans=0;
struct node{
	int to,next;
	node()
	{
		to=next=0;
	}
}a[900100];
int tot=0,N,M;
void add(int from,int to)
{
	tot++;
	a[tot].to=to;
	a[tot].next=head[from];
	head[from]=tot;
}
void DFS(int node,int y)
{
	if(sumt[node]!=0)return;
	if(!chudu[node])
	{
		sumt[y]++;
		return;
	}
	for(int i=head[node];i!=-1;i=a[i].next)
	{
		DFS(a[i].to,node);
		sumt[node]+=sumt[a[i].to];
	}
	if(y==0)ans+=sumt[node];
}
void read(int &q)
{
	int ch=0,x=0;
	while(ch=getchar(),ch<'0'||ch>'9');
	x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	q=x;
}
int main()
{
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	memset(head,-1,sizeof(head));
	scanf("%d%d",&N,&M);
	for(int i=1;i<=M;i++)
	{
		int a,b;
		read(a);read(b);
		add(a,b);
		chudu[a]=1;
		rudu[b]=1;
	}
	int tot=0;
	for(int i=1;i<=N;i++)
	{
		if(!rudu[i]&&chudu[i])DFS(i,0);
	}
	printf("%d",ans);
}