1 /* 2    题目大意：有N个cows, M个关系 3    a->b 表示 a认为b  popular；如果还有b->c, 那么就会有a->c  4    问最终有多少个cows被其他所有cows认为是popular！ 5     6    思路：强连通分量中每两个节点都是可达的！ 通过分解得到最后一个连通分量A， 7    如果将所有的强连通分量看成一个大的节点，那么A一定是孩子节点（因为我们先 8    完成的是父亲节点的强连通分量）! 最后如果其他的强连通分量都可以指向A，那么 9    A中的每一个cow都会被其他cows所有的cows认为popular！ 10 */ 11 #include <string>12 #include <cstdio>13 #include <cstring>14 #include <iostream>15 #include<vector>16 #define M 1000517 using namespace std;18 19 vector<int>ex[M];20 vector<int>ey[M];21 22 int n, m;23 int cnt[M];//记录第一次dfs的节点的逆序24 int vis[M];//标记节点是否已经被访问过了25 int mark[M];//标记每一个节点是属于哪一个连通分量26 int ans;27 int top;28 29 void dfs1(int u){//出度遍历 30     if(!vis[u]){31        vis[u]=1;32        int len=ex[u].size();33        for(int i=0; i<len; ++i){34            int v=ex[u][i];35            dfs1(v);36        }37        cnt[top++]=u;38     }39 }40 41 void dfs2(int u){//入度遍历 42    if(!vis[u]){43       vis[u]=1;44       mark[u]=ans;45       int len=ey[u].size();46       for(int i=0; i<len; ++i){47          int v=ey[u][i];48          dfs2(v);49       }50    }51 }52 53 int main(){54    while(scanf("%d%d", &n, &m)!=EOF){55       while(m--){56          int u, v;57          scanf("%d%d", &u, &v);58          ex[u].push_back(v);59          ey[v].push_back(u);60       }61       ans=top=0;62       for(int i=1; i<=n; ++i)63          if(!vis[i])64              dfs1(i);65       66       memset(vis, 0, sizeof(vis));67 68       for(int i=top-1; i>=0;  --i)69           if(!vis[cnt[i]]){70              ++ans;71              dfs2(cnt[i]);72           }73       int count=0;74       int u=0;75       for(int i=1; i<=n; ++i)76            if(mark[i]==ans){77               ++count;78               u=i;79            }80       memset(vis, 0, sizeof(vis));81       dfs2(u);82 83       for(int i=1; i<=n; ++i)//其他的强连通分量是否都指向了最后一个强连通分量 84         if(!vis[i]){85            count=0;86            break;87         }88       printf("%d\n", count);89       for(int i=1; i<=n; ++i){90          ex[i].clear();91          ey[i].clear();92       }93       memset(vis, 0, sizeof(vis));94    }95    return 0;96 }