割点和桥笔记

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
10 
11 
12 
13 
14 
15 
16 
17 
18 
19 
20 
21 
22 
23 

void tarjan(int u, int father) { 
 int child = 0; 
 vis[u] = 1; 
 low[u] = dfn[u] = ++inde; 
 for (int i = 0; i < g[u].size(); i++) { 
 int v = g[u][i]; 
 if (!vis[v]) { 
 child++; 
 tarjan(v, u); 
 low[u] = min(low[u], low[v]); 
 if (father != u && low[v] >= dfn[u] && !flag[u]) { 
 flag[u] = 1; 
 res++; 
 } 
 } else if (v != father) { 
 low[u] = min(low[u], dfn[v]); 
 } 
 } 
 if (u == father && child >= 2 && !flag[u]) { // 特判根节点 
 flag[u] = 1; 
 res++; 
 } 
} 

 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
10 
11 
12 
13 
14 
15 
16 
17 

void tarjan(int u, int fa) { 
 father[u] = fa; 
 low[u] = dfn[u] = ++inde; 
 for (int i = 0; i < G[u].size(); i++) { 
 int v = G[u][i]; 
 if (!dfn[v]) { 
 tarjan(v, u); 
 low[u] = min(low[u], low[v]); 
 if (low[v] > dfn[u]) { 
 isbridge[v] = true; 
 ++cnt_bridge; 
 } 
 } else if (dfn[v] < dfn[u] && v != fa) { 
 low[u] = min(low[u], dfn[v]); 
 } 
 } 
}