1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 #include<set> 
 5 
 6 using namespace std;
 7 
 8 int daan,n,m,head[10001],tot;
 9 int dfn[10001],low[10001],sum,rp;
10 int belong[10001],_head[10001],num[10001];
11 bool vis[10001];
12 struct kk{
13     int to,next;
14 }e[50001],a[50001];
15 stack<int> s;
16 set<int> ans[10001];
17 
18 inline void add(int x,int y) {
19     e[++tot].to = y;
20     e[tot].next = head[x];
21     head[x] = tot; 
22 }
23 
24 inline void tarjan(int x) {
25     dfn[x] = low[x] = ++sum;
26     int v;
27     s.push(x);
28     vis[x] = 1;
29     for(int i = head[x];i != 0; i = e[i].next) {
30         v = e[i].to;
31         if(!dfn[v]) {
32             tarjan(v);
33             low[x] = min(low[x],low[v]);
34         }
35         else if(vis[x])
36             low[x] = min(low[x],dfn[v]);
37     }
38     if(dfn[x] == low[x]) {
39         rp++;
40         do {
41             v = s.top();
42             s.pop();
43             belong[v] = rp;
44             num[rp]++;
45             vis[x] = false;
46         }
47         while(v != x);
48     }
49 }
50 
51 inline void _add(int x,int y) {
52     a[++tot].to = y;
53     a[tot].next = _head[x];
54     _head[x] = tot;
55 }
56 
57 inline void findin() {
58     for(int i = 1;i <= rp; i++)
59         for(int j = _head[i];j != 0; j = a[j].next) {
60             int o = a[j].to;
61             ans[i].insert(o);
62         }
63 } 
64 
65 int main() {
66     scanf("%d%d",&n,&m);
67     for(int i = 1;i <= m; i++) {
68         int x,y;
69         scanf("%d%d",&x,&y);
70         add(x,y);
71     }
72     for(int i = 1;i <= n; i++)
73         if(!dfn[i])    //求强连通分量 
74             tarjan(i);
75     tot = 0;
76     for(int i = 1;i <= n; i++)//构建新图,其实没啥必要 
77         for(int j = head[i];j != 0; j = e[j].next)
78             if(belong[i] != belong[e[j].to])
79                 _add(belong[i],belong[e[j].to]);
80     findin();
81     for(int i = 1;i <= rp; i++)//找入度为0的点 
82         if(ans[i].size() == 0) {
83             if(daan != 0)  {
84                 printf("0");
85                 return 0;
86             }
87             daan = i;           
88         }
89     printf("%d",num[daan]);
90     return 0;
91 } 

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<stack>
 4 #include<set> 
 5 
 6 using namespace std;
 7 
 8 int daan,n,m,head[10001],tot;
 9 int _out[10001],dfn[10001],low[10001];
10 int sum,rp,belong[10001];
11 int _head[10001],num[10001];
12 bool vis[10001];
13 struct kk{
14     int to,next;
15 }e[50001],a[50001];
16 stack<int> s;
17 
18 inline void add(int x,int y) {
19     e[++tot].to = y;
20     e[tot].next = head[x];
21     head[x] = tot; 
22 }
23 
24 inline void tarjan(int x) {
25     dfn[x] = low[x] = ++sum;
26     int v;
27     s.push(x);
28     vis[x] = 1;
29     for(int i = head[x];i != 0; i = e[i].next) {
30         v = e[i].to;
31         if(!dfn[v]) {
32             tarjan(v);
33             low[x] = min(low[x],low[v]);
34         }
35         else if(vis[x])
36             low[x] = min(low[x],dfn[v]);
37     }
38     if(dfn[x] == low[x]) {
39         rp++;
40         do {
41             v = s.top();
42             s.pop();
43             belong[v] = rp;
44             num[rp]++;
45             vis[x] = false;
46         }
47         while(v != x);
48     }
49 }
50 
51 inline void _add(int x,int y) {
52     a[++tot].to = y;
53     a[tot].next = _head[x];
54     _head[x] = tot;
55 }
56 
57 int main() {
58     scanf("%d%d",&n,&m);
59     for(int i = 1;i <= m; i++) {
60         int x,y;
61         scanf("%d%d",&x,&y);
62         add(x,y);
63     }
64     for(int i = 1;i <= n; i++)
65         if(!dfn[i])    
66             tarjan(i);
67     tot = 0;
68     for(int i = 1;i <= n; i++) 
69         for(int j = head[i];j != 0; j = e[j].next)
70             if(belong[i] != belong[e[j].to])
71                 _out[belong[i]]++;
72     for(int i = 1;i <= rp; i++)
73         if(_out[i] == 0) {
74             if(daan != 0)  {
75                 printf("0");
76                 return 0;
77             }
78             daan = i;
79         }
80     printf("%d",num[daan]);
81     return 0;
82 }