比赛 至少完成十道练习 评测结果 AAAAAAAAAA
题目名称 食物链 最终得分 100
用户昵称 Ostmbh 运行时间 0.869 s
代码语言 C++ 内存使用 3.37 MiB
提交时间 2017-05-20 21:41:45
显示代码纯文本
#include <vector>
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int Q[100001]={0};
vector<int>B[100001];//后继
vector<int>F[100001];//前驱
queue<int>D;//起点
queue<int>C;//终点
queue<int>E;
int vis[100001]={0};
int main(){
	freopen("chain_2016.in","r",stdin);
	freopen("chain_2016.out","w",stdout);
	int n,m,x,y,c,Ans=0;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
	cin>>x>>y;
	B[x].push_back(y);
	F[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
	if(B[i].empty())
		C.push(i);//终点
	else if(F[i].empty())
		D.push(i);//起点
	vis[i]=F[i].size();
	}
	while(!D.empty()){
	c=D.front();
	D.pop();
	Q[c]=1;
	E.push(c);
	}
	while(!E.empty()){
	c=E.front();
	E.pop();
	for(int i=0;i<B[c].size();i++){
		Q[B[c][i]]+=Q[c];
		vis[B[c][i]]--;
		if(!vis[B[c][i]])
			E.push(B[c][i]);
		}
	}
	while(!C.empty()){
	c=C.front();
	C.pop();
	Ans+=Q[c];
	}
	cout<<Ans<<endl;
return 0;
}