5166. 卢学魔

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #define rep(i,a,b) for(int i=a;i<=b;i++)
 6 #define N 100007
 7 using namespace std;
 8 int n,m,ans,tot,ls[N],val[N];
 9 int rd[N],cd[N];
10 bool vis[N];
11 struct arr{
12     int to,next;
13 }e[N*2];
14 queue<int> q;
15 
16 void Add(int x,int y){
17     e[++tot].to=y;
18     e[tot].next=ls[x];
19     ls[x]=tot;
20 }
21 
22 int main(){
23     scanf("%d%d",&n,&m);
24     rep(i,1,m){
25         int x,y;
26         scanf("%d%d",&x,&y);
27         Add(x,y);
28         rd[y]++;
29         cd[x]++;
30         vis[x]=vis[y]=1;
31     }
32     rep(i,1,n) if(!rd[i]&&vis[i]) q.push(i),val[i]=1;
33     for(;!q.empty();){
34         int now=q.front();
35         q.pop();
36         for(int i=ls[now];i;i=e[i].next){
37             val[e[i].to]+=val[now];
38             rd[e[i].to]--;
39             if(!rd[e[i].to])    q.push(e[i].to);
40         }
41     }
42     rep(i,1,n)    if(!cd[i]) ans+=val[i];
43     printf("%d",ans);
44 }