比赛 |
防止浮躁的小练习v0.7 |
评测结果 |
AAAAAAAAAA |
题目名称 |
食物链 |
最终得分 |
100 |
用户昵称 |
kxxy |
运行时间 |
1.715 s |
代码语言 |
C++ |
内存使用 |
2.99 MiB |
提交时间 |
2016-10-27 16:09:21 |
显示代码纯文本
//草<->1 兔<->2 狐<->3 鼠<->4 猫头鹰<->5
//吃虫的鸟<->6 蜘蛛<->7 蛇<->8 青蛙<->9 食草昆虫<->10.
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
const int maxx=100010;
int in[maxx],out[maxx];
long long cnt[maxx];
vector<int>v[maxx];
queue<int>q;
int n,m,a,b;
int main()
{
freopen("chain_2016.in","r",stdin);
freopen("chain_2016.out","w",stdout);
cin>>n>>m;
for(int i=1;i<=n;i++)
v[i].clear();
for(int i=1;i<=m;i++)
{
cin>>a>>b;
v[a].push_back(b);
in[b]++;
out[a]++;
}
long long ans=0;
for(int i=1;i<=n;i++)
if(!in[i])
{
cnt[i]=1;
q.push(i);
if(!out[i])
ans--;
}
while(!q.empty())
{
int c=q.front();
q.pop();
for(int i=0;i<v[c].size();i++)
{
cnt[v[c][i]]+=cnt[c];
in[v[c][i]]--;
if(!in[v[c][i]])
q.push(v[c][i]);
}
}
for(int i=1;i<=n;i++)
if(!out[i])
ans+=cnt[i];
cout<<ans<<endl;
return 0;
}