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

using namespace std;

const int nmax=200086;

int n,m;
int tmpfrom,tmpto;
int in[nmax]={0};
int out[nmax]={0};

int A[nmax]={0};

int ans=0;

vector<int > G[nmax];

void DFS(int tmpx,int tmpl){
	if(A[tmpx]) return;

	if(out[tmpx]==0){
		A[tmpl]++;
		return;
	}
	for(int i=0;i<G[tmpx].size();i++){
		DFS(G[tmpx][i],tmpx);
		A[tmpx]+=A[G[tmpx][i]];
	}
	if(tmpl==0) ans+=A[tmpx];
}	


void PreDo(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		scanf("%d%d",&tmpfrom,&tmpto);
		in[tmpto]++;
		out[tmpfrom]++;
		G[tmpfrom].push_back(tmpto);
	}
	for(int i=1;i<=n;i++){
		if(in[i]==0&&out[i]!=0){
			DFS(i,0);
		}
	}
	printf("%d\n",ans);
}


int main(){
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	PreDo();
	return 0;
}