邊雙連通分量

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

連接兩個邊雙連通分量的邊即是橋。

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

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

(1) dfn[v];

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

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

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

注意一個割點(diǎn)屬于多個點(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)雙連通分量沒有公共邊，所以彈出這個點(diǎn)雙連通分量里的所有邊就一定包含這里面的所有點(diǎn)，而且一定不含其他點(diǎn)雙連通分量的邊。因此求解時只需彈出這個點(diǎn)雙連通分量里的所有邊，并記錄這些邊的點(diǎn)即可(要判重，一個點(diǎn)可出現(xiàn)多次)，正確。

2.如果存點(diǎn)

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

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

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

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

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

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