割點(diǎn)
割點(diǎn)：如果在圖G中刪去一個(gè)結(jié)點(diǎn)u后，圖G的連通分枝數(shù)增加，即W(G-u)>W(G)，則稱(chēng)結(jié)點(diǎn)u為G的割點(diǎn)，又稱(chēng)關(guān)節(jié)點(diǎn)。
直觀地說(shuō)，就是刪除了連通圖的某點(diǎn)后，圖不在連通，而是分為幾個(gè)連通分量。
性質(zhì)：（1）考慮根節(jié)點(diǎn)Root，如果Root有數(shù)量多于1的子結(jié)點(diǎn)時(shí)，Root是割點(diǎn)。
（2）考慮非根結(jié)點(diǎn)u，當(dāng)且僅當(dāng)u的某個(gè)兒子及兒子的子孫均沒(méi)有指向u的祖先的后向邊時(shí)，u是割點(diǎn)。（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)，則稱(chēng)邊u為G的橋，又稱(chēng)割邊或關(guān)節(jié)邊。
性質(zhì): 對(duì)于一條邊<u,v>，v是u的孩子如果兒子及兒子的子孫均沒(méi)有指向u的祖先的后向邊時(shí)，<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 赤果果的求割點(diǎn)的題。
相關(guān)鏈接:
Beyond the Void的講解，很精彩
推薦閱讀：
lrj的黑書(shū)P285