割點
割點：如果在圖G中刪去一個結(jié)點u后，圖G的連通分枝數(shù)增加，即W(G-u)>W(G)，則稱結(jié)點u為G的割點，又稱關(guān)節(jié)點。
直觀地說，就是刪除了連通圖的某點后，圖不在連通，而是分為幾個連通分量。
性質(zhì)：（1）考慮根節(jié)點Root，如果Root有數(shù)量多于1的子結(jié)點時，Root是割點。
（2）考慮非根結(jié)點u，當(dāng)且僅當(dāng)u的某個兒子及兒子的子孫均沒有指向u的祖先的后向邊時，u是割點。（LOW[v]>=DFN[u],v是u的孩子）
代碼：
1 void DFS(int cur,int par)
2 {
3 dfn[cur]=low[cur]=++Index;
4
5 int size=adj[cur].size();
6 int cnt=0;
7 for(int i=0;i<size;i++)
8 {
9 int v=adj[cur][i];
10 if(!dfn[v])
11 {
12 cnt++;
13 DFS(v,cur);
14 if(low[cur]>low[v])
15 low[cur]=low[v];
16 if((cur==root&&cnt==2)||(cur!=root&&low[v]>=dfn[cur]))
17 flag[cur]=true;
18 }
19 else if(v!=par&&low[cur]>dfn[v])
20 low[cur]=dfn[v];
21 }
22 }
23
割邊
割邊：如果在圖G中刪去一條邊e后，圖G的連通分支數(shù)增加，即W(G-e)>W(G)，則稱邊u為G的橋，又稱割邊或關(guān)節(jié)邊。
性質(zhì): 對于一條邊<u,v>，v是u的孩子如果兒子及兒子的子孫均沒有指向u的祖先的后向邊時，<u,v>是割邊。（LOW[v]>DFN[u]）
代碼：
1 void CutEdge(int cur,int par)
2 { dfn[cur]=low[cur]=++Index;
3
4 for(int i=head[cur];i;i=buf[i].next)
5 {
6 int v=buf[i].v;
7 if(v==par)continue;
8 if(!dfn[v])
9 {
10 CutEdge(v,cur);
11 if(low[cur]>low[v])
12 low[cur]=low[v];
13 if(low[v]>dfn[cur])
14 {
15 ans[nAns++]=buf[i].id;
16 }
17 }
18 else if(low[cur]>dfn[v])
19 low[cur]=dfn[v];
20 }
21 }
相關(guān)習(xí)題：
POJ 1144 Network 赤果果的求割點的題。
相關(guān)鏈接:
Beyond the Void的講解，很精彩
推薦閱讀：
lrj的黑書P285