並查集應用

並查集，Kruskal 重構樹的思維方式是很類似的，他們都能用於處理與連通性有關的問題。本文通過例題講解的方式給大家介紹並查集思想的應用。

A

有 \(n\) 個點，初始時均為孤立點。

接下來有 \(m\) 次加邊操作，第 \(i\) 次操作在 \(a_i\) 和 \(b_i\) 之間加一條無向邊。設 \(L(i,j)\) 表示結點 \(i\) 和 \(j\) 最早在第 \(L(i,j)\) 次操作後連通。

在 \(m\) 次操作完後，你要求出 \(\sum_{i=1}^n\sum_{j=i+1}^nL(i,j)\) 的值。

這是基礎並查集的應用，並查集記錄一下子樹的大小。考慮統計每次操作的貢獻。如果第 \(i\) 次操作 \(a_i\) 和 \(b_i\) 分屬於兩個不同子樹，就將這兩個子樹合併，並將兩者子樹大小的乘積乘上 \(i\) 累加到答案裏。時間複雜度 \(O(n\alpha(n))\)。

B

有 \(n\) 個點，初始時均為孤立點。

接下來有 \(m\) 次加邊操作，第 \(i\) 次操作在 \(a_i\) 和 \(b_i\) 之間加一條無向邊。

接下來有 \(q\) 次詢問，第 \(i\) 次詢問 \(u_i\) 和 \(v_i\) 最早在第幾次操作後連通。

考慮在並查集合並的時候記錄「並查集生成樹」，也就是説如果第 \(i\) 次操作 \(a_i\) 和 \(b_i\) 分屬於兩個不同子樹，那麼把 \((a_i,b_i)\) 這條邊納入生成樹中。邊權是 \(i\)。那麼查詢就是詢問 \(u\) 到 \(v\) 路徑上邊權的最大值，可以使用樹上倍增或者樹鏈剖分的方法維護。時間複雜度 \(O(n\log n)\)。

另外一個方法是維護 Kruskal 重構樹，其本質與並查集生成樹是相同的。複雜度亦相同。

C

有 \(n\) 個點，初始時均為孤立點。

接下來有 \(m\) 次加邊操作，第 \(i\) 次操作在 \(a_i\) 和 \(b_i\) 之間加一條無向邊。

接下來有 \(q\) 次詢問，第 \(i\) 次詢問第 \(x_i\) 個點在第 \(t_i\) 次操作後所在連通塊的大小。

離線算法：考慮將詢問按 \(t_i\) 從小到大排序。在加邊的過程中使用並查集順便處理詢問即可。時間複雜度 \(O(q\log q+(n+q)\alpha(n))\)。

在線算法：本題的在線算法只能使用 Kruskal 重構樹。Kruskal 重構樹與並查集的區別是：第 \(i\) 次操作 \(a_i\) 和 \(b_i\) 分屬於兩個不同子樹，那麼 Kruskal 會新建一個結點 \(u\)，然後讓 \(a_i\) 所在子樹的根和 \(b_i\) 所在子樹的根分別連向 \(u\)，作為 \(u\) 的兩個兒子。不妨設 \(u\) 的點權是 \(i\)。對於初始的 \(n\) 個點，點權為 \(0\)。

對於詢問，我們只需要求出 \(x_i\) 在重構樹中最大的一個連通塊使得連通中的點權最大值不超過 \(t_i\)，詢問的答案就是這個連通塊中點權為 \(0\) 的結點個數，即葉子結點個數。

由於我們操作的編號是遞增的，因此重構樹上父結點的點權總是大於子結點的點權。這意味着我們可以在重構樹上從 \(x_i\) 到根結點的路徑上倍增找到點權最大的不超過 \(t_i\) 的結點。這樣我們就求出了答案。時間複雜度 \(O(n\log n)\)。

D

給一個長度為 \(n\) 的 01 序列 \(a_1,\ldots,a_n\)，一開始全是 \(0\)，接下來進行 \(m\) 次操作：

令 \(a_x=1\)；
求 \(a_x,a_{x+1},\ldots,a_n\) 中左數第一個為 \(0\) 的位置。

建立一個並查集，\(f_i\) 表示 \(a_i,a_{i+1},\ldots,a_n\) 中第一個 \(0\) 的位置。初始時 \(f_i=i\)。

對於一次 \(a_x=1\) 的操作，如果 \(a_x\) 原本就等於 \(1\)，就不管。否則我們令 \(f_x=f_{x+1}\)。

時間複雜度 \(O(n\log n)\)，如果要使用按秩合併的話實現會較為麻煩，不過仍然可行。也就是説時間複雜度或為 \(O(n\alpha(n))\)。

E

給出三個長度為 \(n\) 的正整數序列 \(a\)，\(b\)，\(c\)。枚舉 \(1\le i\le j\le n\)，求 \(a_i\cdot b_j\cdot \min_{i\le k\le j}c_k\) 的最大值。

本題同樣有許多做法，這裏我們重點講解並查集思路。按權值從大到小考慮 \(c_k\)。相當於我們在 \(k\) 上加入一個點，然後將 \(k-1\) 和 \(k+1\) 位置上的點所在的連通塊與之合併（如果這兩個位置上有點的話）。連通塊上記錄 \(a\) 的最大值和 \(b\) 的最大值，即可在合併的時候更新答案。時間複雜度 \(O(n\log n)\)。

F

給出一棵 \(n\) 個點的樹，接下來有 \(m\) 次操作：

加一條從 \(a_i\) 到 \(b_i\) 的邊。
詢問兩個點 \(u_i\) 和 \(v_i\) 之間是否有至少兩條邊不相交的路徑。

詢問可以轉化為：求 \(u_i\) 和 \(v_i\) 是否在同一個簡單環上。按照雙連通分量縮點的想法，每次我們在 \(a_i\) 和 \(b_i\) 間加一條邊，就可以把 \(a_i\) 到 \(b_i\) 樹上路徑的點縮到一起。如果兩條邊 \((a_i,b_i)\) 和 \((a_j,b_j)\) 對應的樹上路徑有交，那麼這兩條邊就會被縮到一起。

換言之，加邊操作可以理解為，將 \(a_i\) 到 \(b_i\) 樹上路徑的邊覆蓋一次。而詢問就轉化為了：判斷 \(u_i\) 到 \(v_i\) 路徑上是否存在未被覆蓋的邊。如果不存在，那麼 \(u_i\) 和 \(v_i\) 就屬於同一個雙連通分量，也就屬於同一個簡單環。

考慮使用並查集維護。給樹定根，設 \(f_i\) 表示 \(i\) 到根的路徑中第一個未被覆蓋的邊。那麼每次加邊操作，我們就暴力跳並查集。覆蓋了一條邊後，將這條邊對應結點的 \(f\) 與父節點合併。這樣，每條邊至多被覆蓋一次，總複雜度 \(O(n\log n)\)。使用按秩合併的並查集同樣可以做到 \(O(n\alpha(n))\)。

本題的維護方式類似於 D 的樹上版本。

G

無向圖 \(G\) 有 \(n\) 個點，初始時均為孤立點（即沒有邊）。

接下來有 \(m\) 次加邊操作，第 \(i\) 次操作在 \(a_i\) 和 \(b_i\) 之間加一條無向邊。

每次操作後，你均需要求出圖中橋的個數。

橋的定義為：對於一條 \(G\) 中的邊 \((x,y)\)，如果刪掉它會使得連通塊數量增加，則 \((x,y)\) 被稱作橋。

強制在線。

本題考察對並查集性質的理解。考慮用並查集維護連通情況。對於邊雙樹，考慮維護有根樹，設 \(p_i\) 表示結點 \(i\) 的父親。也就是不帶路徑壓縮的並查集。

如果第 \(i\) 次操作 \(a_i\) 和 \(b_i\) 屬於同一個連通塊，那麼我們就需要將邊雙樹上 \(a_i\) 到 \(b_i\) 路徑上的點縮起來。這可以用並查集維護。每次縮點，邊雙連通分量的個數減少 \(1\)，最多減少 \(n-1\) 次，因此縮點部分的並查集複雜度是 \(O(n\alpha(n))\)。

為了縮點，我們要先求出 \(a_i\) 和 \(b_i\) 在邊雙樹上的 LCA。對此我們可以維護一個標記數組。然後從 \(a_i\) 和 \(b_i\) 開始輪流沿着祖先一個一個往上跳，並標記沿途經過的點。一但跳到了某個之前就被標記過的點，那麼這個點就是 \(a_i\) 和 \(b_i\) 的 LCA。這個算法的複雜度與 \(a_i\) 到 \(b_i\) 的路徑長度是線性相關的，可以接受。

如果 \(a_i\) 和 \(b_i\) 分屬於兩個不同連通塊，那麼我們將這兩個連通塊合併，並且橋的數量加 \(1\)。此時我們需要將兩個點所在的邊雙樹連起來，也就是加一條 \(a_i\) 到 \(b_i\) 的邊。因此我們需要將其中一棵樹重新定根，然後接到另一棵樹上。這裏運用啓發式合併的思想：我們把結點數更小的重新定根。這樣的總複雜度是 \(O(n\log n)\) 的。

綜上，該算法的總複雜度是 \(O(n\log n+m\log n)\) 的。

小結

並查集與 Kruskal 重構樹有許多共通點，而並查集的優化（按秩合併）正是啓發式合併思想的應用。因此靈活運用並查集可以方便地處理許多與連通性有關的圖論問題。

本頁面部分內容譯自博文 Поиск мостов в режиме онлайн 與其英文翻譯版 Finding Bridges Online。其中俄文版版權協議為 Public Domain + Leave a Link；英文版版權協議為 CC-BY-SA 4.0。

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