跳转至

雙連通分量

簡介

在閲讀下列內容之前，請務必瞭解 圖論相關概念 部分。

相關閲讀：割點和橋

定義

割點和橋更嚴謹的定義參見 圖論相關概念。

在一張連通的無向圖中，對於兩個點 \(u\) 和 \(v\)，如果無論刪去哪條邊（只能刪去一條）都不能使它們不連通，我們就説 \(u\) 和 \(v\) 邊雙連通。

在一張連通的無向圖中，對於兩個點 \(u\) 和 \(v\)，如果無論刪去哪個點（只能刪去一個，且不能刪 \(u\) 和 \(v\) 自己）都不能使它們不連通，我們就説 \(u\) 和 \(v\) 點雙連通。

邊雙連通具有傳遞性，即，若 \(x,y\) 邊雙連通，\(y,z\) 邊雙連通，則 \(x,z\) 邊雙連通。

點雙連通 不 具有傳遞性，反例如下圖，\(A,B\) 點雙連通，\(B,C\) 點雙連通，而 \(A,C\) 不 點雙連通。

bcc-counterexample.png

DFS

對於一張連通的無向圖，我們可以從任意一點開始 DFS，得到原圖的一棵生成樹（以開始 DFS 的那個點為根），這棵生成樹上的邊稱作 樹邊，不在生成樹上的邊稱作 非樹邊。

由於 DFS 的性質，我們可以保證所有非樹邊連接的兩個點在生成樹上都滿足其中一個是另一個的祖先。

DFS 的代碼如下：

實現 
1
2
3
4
5
void DFS(int p) {
  visited[p] = true;
  for (int to : edge[p])
    if (!visited[to]) DFS(to);
}

1
2
3
4
5
def DFS(p):
    visited[p] = True
    for to in edge[p]:
        if visited[to] == False:
            DFS(to)

過程

DFS 找橋並判斷邊雙連通

首先，對原圖進行 DFS。

bcc-1.png

如上圖所示，黑色與綠色邊為樹邊，紅色邊為非樹邊。每一條非樹邊連接的兩個點都對應了樹上的一條簡單路徑，我們説這條非樹邊 覆蓋 了這條樹上路徑上所有的邊。綠色的樹邊 至少 被一條非樹邊覆蓋，黑色的樹邊不被 任何 非樹邊覆蓋。

我們如何判斷一條邊是不是橋呢？顯然，非樹邊和綠色的樹邊一定不是橋，黑色的樹邊一定是橋。

如何用算法去實現以上過程呢？首先有一個比較暴力的做法，對於每一條非樹邊，都逐個地將它覆蓋的每一條樹邊置成綠色，這樣的時間複雜度為 \(O(nm)\)。

怎麼優化呢？可以用差分。對於每一條非樹邊，在其樹上深度較小的點處打上 -1 標記，在其樹上深度較大的點處打上 +1 標記。然後 \(O(n)\) 求出每個點的子樹內部的標記之和。對於一個點 \(u\)，其子樹內部的標記之和等於覆蓋了 \(u\) 和 \(u\) 的父親之間的樹邊的非樹邊數量。若這個值非 \(0\)，則 \(u\) 和 \(u\) 的父親之間的樹邊不是橋，否則是橋。

用以上的方法 \(O(n+m)\) 求出每條邊分別是否是橋後，兩個點是邊雙連通的，當且僅當它們的樹上路徑中 不 包含橋。

DFS 找割點並判斷點雙連通

bcc-2.png

如上圖所示，黑色邊為樹邊，紅色邊為非樹邊。每一條非樹邊連接的兩個點都對應了樹上的一條簡單路徑。

考慮一張新圖，新圖中的每一個點對應原圖中的每一條樹邊（在上圖中用藍色點表示）。對於原圖中的每一條非樹邊，將這條非樹邊對應的樹上簡單路徑中的所有邊在新圖中對應的藍點連成一個連通塊（這在上圖中也用藍色的邊體現出來了）。

這樣，一個點不是割點，當且僅當與其相連的所有邊在新圖中對應的藍點都屬於同一個連通塊。兩個點點雙連通，當且僅當它們在原圖的樹上路徑中的所有邊在新圖中對應的藍點都屬於同一個連通塊。

藍點間的連通關係可以用與求邊雙連通時用到的差分類似的方法維護，時間複雜度 \(O(n+m)\)。

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用