洛谷 P3183 [HAOI2016]食物链

题目传送门

解题思路:

跟另一个题差不多,就是本题单独一个生物不算一条食物链.

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<queue>
 5 
 6 using namespace std;
 7 
 8 int n,m,_in[100001],f[100001],_out[100001],ans;
 9 vector<int> a[100001];
10 bool vis[100001];
11 queue<int> q;
12 
13 inline void solve(int fa) {
14     q.push(fa);
15     f[fa] = 1;
16     while(!q.empty()) {
17         int u = q.front();
18         q.pop();
19         for(int i = 0;i < a[u].size(); i++) {
20             f[a[u][i]] = f[a[u][i]] + f[u];
21             _in[a[u][i]]--;
22             if(_in[a[u][i]] == 0)
23                 q.push(a[u][i]);
24         }
25     }
26 }
27 
28 int main() {
29     scanf("%d%d",&n,&m);
30     for(int i = 1;i <= m; i++) {
31         int x,y;
32         scanf("%d%d",&x,&y);
33         _in[y]++;_out[x]++;
34         a[x].push_back(y);
35         vis[y] = 1;
36     }
37     for(int i = 1;i <= n; i++) 
38         if(!vis[i])
39             solve(i);
40     for(int i = 1;i <= n; i++) 
41         if(_out[i] == 0 && vis[i])
42             ans += f[i];
43     printf("%d",ans);
44     return 0;
45 }