1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 20100;18 int dfn[maxn],low[maxn],belong[maxn];19 bool instack[maxn];20 vector<int>g[maxn];21 stack<int>stk;22 int n,m,cnt,scc;23 void tarjan(int u) {24     dfn[u] = low[u] = ++cnt;25     stk.push(u);26     instack[u] = true;27     for(int i = 0; i < g[u].size(); i++) {28         if(!dfn[g[u][i]]) {29             tarjan(g[u][i]);30             low[u] = min(low[u],low[g[u][i]]);31         } else if(instack[g[u][i]]) low[u] = min(low[u],dfn[g[u][i]]);32     }33     if(dfn[u] == low[u]) {34         scc++;35         int v;36         do {37             v = stk.top();38             instack[v] = false;39             belong[v] = scc;40             stk.pop();41         } while(v != u);//每一个强连通块内de点，以及其属于的scc42     }43 }44 int main() {45     int i,j,u,v,a,b;46     while(~scanf("%d %d",&n,&m)) {47         for(i = 0; i <= n; i++) {48             dfn[i] = belong[i] = 0;49             instack[i] = false;50             g[i].clear();51         }52         cnt = scc = 0;53         while(!stk.empty()) stk.pop();54         for(i = 1; i <= m; i++) {55             scanf("%d %d",&u,&v);56             g[u].push_back(v);57         }58         for(i = 1; i <= n; i++)59             if(!dfn[i]) tarjan(i);60     }61     return 0;62 }