有人说这篇博客不是很友好，所以我加了点解释，感觉是不是友好多了？
dfn[u]表示节点u在dfs时被访问的次序。
low[u]表示节点u能够追溯到的最远的祖先的dfn。
ins[u]表示节点u是否在栈中。
belong[u]表示节点u所属的SCC标号，也可以说可以缩成的点的标号。
若u的子节点v可以追溯到节点x(x可能为u的祖先)，那么u也可以追溯到节点x。
同时如果是最远祖先那么祖先在dfs中的顺序肯定最小，所以取min值。
如果搜索到的点已经在栈中了，那么当前点的祖先肯定可以是在栈中的点。
1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 5 int n, m, cnt, index, ans, size; 6 int head[10001], to[10001], next[10001], dfn[10001], low[10001], belong[10001]; 7 bool ins[10001]; 8 std::stack <int> s; 9 10 inline void add(int x, int y) 11 { 12 to[cnt] = y; 13 next[cnt] = head[x]; 14 head[x] = cnt++; 15 } 16 17 void tarjan(int u) 18 { 19 dfn[u] = low[u] = ++index; 20 s.push(u); 21 ins[u] = 1; 22 int i, v; 23 for(i = head[u]; i != -1; i = next[i]) 24 { 25 v = to[i]; 26 if(!dfn[v]) 27 { 28 tarjan(v); 29 low[u] = std::min(low[u], low[v]); 30 } 31 else if(ins[v]) low[u] = std::min(low[u], dfn[v]); 32 } 33 if(low[u] == dfn[u]) 34 { 35 size++; 36 do 37 { 38 v = s.top(); 39 ins[v] = 0; 40 belong[v] = size; 41 s.pop(); 42 }while(v != u); 43 } 44 } 45 46 int main() 47 { 48 int i, x, y; 49 scanf("%d %d", &n, &m); 50 memset(head, -1, sizeof(head)); 51 for(i = 1; i <= m; i++) 52 { 53 scanf("%d %d", &x, &y); 54 add(x, y); 55 } 56 for(i = 1; i <= n; i++)//有可能是非连通图 57 if(!dfn[i]) 58 tarjan(i); 59 printf("%d ", size); 60 for(i = 1; i <= n; i++) printf("%d ", belong[i]); 61 return 0; 62 }