比赛 防止浮躁的小练习v0.7 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 Hzoi_Go灬Fire 运行时间 0.500 s
代码语言 C++ 内存使用 21.07 MiB
提交时间 2016-10-27 18:05:42
显示代码纯文本
#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=1010000;
struct Edge{
	int next,to;
}e[maxn];
int head[maxn],len,ans,chudu[maxn],rudu[maxn],tot[maxn];
int n,m;
void Init();
void Insert(int x,int y){
	len++;e[len].to=y;e[len].next=head[x];chudu[x]++;rudu[y]++;head[x]=len; 
}
void Dfs(int x){
	if(chudu[x]==0){
		tot[x]=1;return;
	}
	if(tot[x])return;
	for(int i=head[x];i;i=e[i].next){
		Dfs(e[i].to),tot[x]+=tot[e[i].to];
	}
}
int main(){
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
    Init();
    //system("pause");
    return 0;
}
void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;scanf("%d%d",&x,&y);
		Insert(y,x);
	}
	for(int i=1;i<=n;i++){
		if(!rudu[i] && chudu[i]){
			Dfs(i);
			ans+=tot[i];
		}
	}
	printf("%d\n",ans);
}