比赛 |
近期练习题回顾 |
评测结果 |
AAAAAAAAAA |
题目名称 |
食物链 |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
0.432 s |
代码语言 |
C++ |
内存使用 |
17.19 MiB |
提交时间 |
2018-10-16 12:17:32 |
显示代码纯文本
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
vector<int>b[100010];
int n,m,a1,a2,r[100010];
long long f[100010],ans=0;
bool bk[100010];
inline void dfs(int p){
bk[p]=1;
if(!b[p].size())return;
for(int i=0;i<b[p].size();i++)f[b[p][i]]+=f[p],r[b[p][i]]--;
for(int i=0;i<b[p].size();i++)if(!r[b[p][i]]&&!bk[b[p][i]])dfs(b[p][i]);
return;
}
int main(){
freopen("chain_2016.in","r",stdin);
freopen("chain_2016.out","w",stdout);
scanf("%d%d",&n,&m);
if(m)for(int i=1;i<=m;i++){
scanf("%d%d",&a1,&a2);
b[a1].push_back(a2);
r[a2]++;
}
for(int i=1;i<=n;i++)if(r[i]==0&&!bk[i]){
if(!b[i].size())continue;
f[i]=1,dfs(i);
}
for(int i=1;i<=n;i++)if(!b[i].size())ans+=f[i];
printf("%lld",ans);
return 0;
}