比赛 |
至少完成十道练习 |
评测结果 |
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;
}