比赛 |
防止浮躁的小练习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;
- }