雙連通分量

若一個(gè)無向圖中的去掉任意一條邊都不會(huì)改變此圖的連通性，即不存在橋，則稱作邊雙連通圖。一個(gè)無向圖中的每一個(gè)極大邊雙連通子圖稱作此無向圖的邊雙連通分量。

連接兩個(gè)邊雙連通分量的邊即是橋。

注意:如果圖中有重邊，且允許兩個(gè)點(diǎn)形成一個(gè)環(huán)，則需修改對(duì)能否訪問父節(jié)點(diǎn)的判斷，即若當(dāng)前邊指向父節(jié)點(diǎn)，但不是從父節(jié)點(diǎn)走到當(dāng)前點(diǎn)的邊，則可以用父節(jié)點(diǎn)的dfn更新當(dāng)前點(diǎn)的low。

注意:此代碼不會(huì)將獨(dú)立點(diǎn)記做一個(gè)連通分量。

1. 對(duì)圖進(jìn)行先深搜索，計(jì)算每一個(gè)結(jié)點(diǎn)v的先深標(biāo)號(hào)dfn[v]。

2. 計(jì)算所有結(jié)點(diǎn)v的low[v]是在先深生成樹上按照后根遍歷的順序進(jìn)行的。因此，當(dāng)訪問結(jié)點(diǎn)v時(shí)它的每個(gè)兒子y的low[y]已經(jīng)計(jì)算完畢，這時(shí)low[v]取下面三值中最小者:

(1) dfn[v];

(2) dfn[w], 凡是有回退邊(v, w)的任何結(jié)點(diǎn)w;

(3) low[y],對(duì)v的任何兒子y.

若一個(gè)無向圖中的去掉任意一個(gè)節(jié)點(diǎn)都不會(huì)改變此圖的連通性，即不存在割點(diǎn)，則稱作點(diǎn)雙連通圖。一個(gè)無向圖中的每一個(gè)極大點(diǎn)雙連通子圖稱作此無向圖的點(diǎn)雙連通分量。

注意一個(gè)割點(diǎn)屬于多個(gè)點(diǎn)雙連通分量。

這是初學(xué)者常見的問題，證明如下:

首先要明確邊雙連通分量和點(diǎn)雙連通分量的區(qū)別與聯(lián)系

1.二者都是基于無向圖

2.邊雙連通分量是刪邊后還連通，而后者是刪點(diǎn)

3.點(diǎn)雙連通分量一定是邊雙連通分量(除兩點(diǎn)一線的特殊情況)，反之不一定

4.點(diǎn)雙連通分量可以有公共點(diǎn)，而邊雙連通分量不能有公共邊

由于4，顯然，求解邊雙連通分量只需先一遍dfs求橋，在一遍dfs求點(diǎn)(不經(jīng)過橋即可)

但如果求點(diǎn)雙連通分量，就要更復(fù)雜:

1.如果存邊

根據(jù)dfs的性質(zhì)，每條邊都有且只有一次入棧，而由于性質(zhì)3和性質(zhì)4，點(diǎn)雙連通分量沒有公共邊，所以彈出這個(gè)點(diǎn)雙連通分量里的所有邊就一定包含這里面的所有點(diǎn)，而且一定不含其他點(diǎn)雙連通分量的邊。因此求解時(shí)只需彈出這個(gè)點(diǎn)雙連通分量里的所有邊，并記錄這些邊的點(diǎn)即可(要判重，一個(gè)點(diǎn)可出現(xiàn)多次)，正確。

2.如果存點(diǎn)

根據(jù)dfs的性質(zhì)，每個(gè)點(diǎn)同樣有且只有一次入棧。但注意，由于性質(zhì)4，你將一個(gè)點(diǎn)出棧后，還可能有別的點(diǎn)雙連通分量包含它，錯(cuò)誤。

有向圖的最大強(qiáng)連通子圖稱為該有向圖的強(qiáng)連通分量。

強(qiáng)連通圖只有一個(gè)強(qiáng)連通分量，即本身，非強(qiáng)連通圖有多個(gè)強(qiáng)連通分量。

任何連通圖的連通分量只有一個(gè)，即為其本身。