天天看點

【算法】算法學習筆記: 并查集【轉載】

原文連結:https://zhuanlan.zhihu.com/p/93647900

前言

并查集被很多OIer認為是最簡潔而優雅的資料結構之一,主要用于解決一些元素分組的問題。它管理一系列不相交的集合,并支援兩種操作:

  • 合并(Union):把兩個不相交的集合合并為一個集合。
  • 查詢(Find):查詢兩個元素是否在同一個集合中。

    當然,這樣的定義未免太過學術化,看完後恐怕不太能了解它具體有什麼用。是以我們先來看看并查集最直接的一個應用場景:親戚問題。

(洛谷P1551)親戚

題目背景

若某個家族人員過于龐大,要判斷兩個是否是親戚,确實還很不容易,現在給出某個親戚關系圖,求任意給出的兩個人是否具有親戚關系。

題目描述

規定:x和y是親戚,y和z是親戚,那麼x和z也是親戚。如果x,y是親戚,那麼x的親戚都是y的親戚,y的親戚也都是x的親戚。

輸入格式

第一行:三個整數n,m,p,(n<=5000,m<=5000,p<=5000),分别表示有n個人,m個親戚關系,詢問p對親戚關系。

以下m行:每行兩個數Mi,Mj,1<=Mi,Mj<=N,表示Mi和Mj具有親戚關系。

接下來p行:每行兩個數Pi,Pj,詢問Pi和Pj是否具有親戚關系。

輸出格式

P行,每行一個’Yes’或’No’。表示第i個詢問的答案為“具有”或“不具有”親戚關系。

這其實是一個很有現實意義的問題。我們可以建立模型,把所有人劃分到若幹個不相交的集合中,每個集合裡的人彼此是親戚。為了判斷兩個人是否為親戚,隻需看它們是否屬于同一個集合即可。是以,這裡就可以考慮用并查集進行維護了。

一、并查集的引入

并查集的重要思想在于,用集合中的一個元素代表集合。我曾看過一個有趣的比喻,把集合比喻成幫派,而代表元素則是幫主。接下來我們利用這個比喻,看看并查集是如何運作的。

【算法】算法學習筆記: 并查集【轉載】

最開始,所有大俠各自為戰。他們各自的幫主自然就是自己。(對于隻有一個元素的集合,代表元素自然是唯一的那個元素)

現在1号和3号比武,假設1号赢了(這裡具體誰赢暫時不重要),那麼3号就認1号作幫主(合并1号和3号所在的集合,1号為代表元素)。

【算法】算法學習筆記: 并查集【轉載】

現在2号想和3号比武(合并3号和2号所在的集合),但3号表示,别跟我打,讓我幫主來收拾你(合并代表元素)。不妨設這次又是1号赢了,那麼2号也認1号做幫主。

【算法】算法學習筆記: 并查集【轉載】

現在我們假設4、5、6号也進行了一番幫派合并,江湖局勢變成下面這樣:

【算法】算法學習筆記: 并查集【轉載】

現在假設2号想與6号比,跟剛剛說的一樣,喊幫主1号和4号出來打一架(幫主真辛苦啊)。1号勝利後,4号認1号為幫主,當然他的手下也都是跟着投降了。

【算法】算法學習筆記: 并查集【轉載】

好了,比喻結束了。如果你有一點圖論基礎,相信你已經覺察到,這是一個樹狀的結構,要尋找集合的代表元素,隻需要一層一層往上通路父節點(圖中箭頭所指的圓),直達樹的根節點(圖中橙色的圓)即可。根節點的父節點是它自己。我們可以直接把它畫成一棵樹:

【算法】算法學習筆記: 并查集【轉載】

(好像有點像個火柴人?)

用這種方法,我們可以寫出最簡單版本的并查集代碼。

初始化

int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}
           

假如有編号為1, 2, 3, …, n的n個元素,我們用一個數組fa[]來存儲每個元素的父節點(因為每個元素有且隻有一個父節點,是以這是可行的)。一開始,我們先将它們的父節點設為自己。

查詢

int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}
           

我們用遞歸的寫法實作對代表元素的查詢:一層一層通路父節點,直至根節點(根節點的标志就是父節點是本身)。要判斷兩個元素是否屬于同一個集合,隻需要看它們的根節點是否相同即可。

合并

inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}
           

合并操作也是很簡單的,先找到兩個集合的代表元素,然後将前者的父節點設為後者即可。當然也可以将後者的父節點設為前者,這裡暫時不重要。本文末尾會給出一個更合理的比較方法。

二、路徑壓縮

最簡單的并查集效率是比較低的。例如,來看下面這個場景:

【算法】算法學習筆記: 并查集【轉載】

現在我們要merge(2,3),于是從2找到1,fa[1]=3,于是變成了這樣:

【算法】算法學習筆記: 并查集【轉載】

然後我們又找來一個元素4,并需要執行merge(2,4):

【算法】算法學習筆記: 并查集【轉載】

從2找到1,再找到3,然後fa[3]=4,于是變成了這樣:

【算法】算法學習筆記: 并查集【轉載】

大家應該有感覺了,這樣可能會形成一條長長的鍊,随着鍊越來越長,我們想要從底部找到根節點會變得越來越難。

怎麼解決呢?我們可以使用路徑壓縮的方法。既然我們隻關心一個元素對應的根節點,那我們希望每個元素到根節點的路徑盡可能短,最好隻需要一步,像這樣:

【算法】算法學習筆記: 并查集【轉載】

其實這說來也很好實作。隻要我們在查詢的過程中,把沿途的每個節點的父節點都設為根節點即可。下一次再查詢時,我們就可以省很多事。這用遞歸的寫法很容易實作:

合并(路徑壓縮)

int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父節點設為根節點
        return fa[x];         //傳回父節點
    }
}
           

以上代碼常常簡寫為一行:

int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
           

注意指派運算符=的優先級沒有三元運算符?:高,這裡要加括号。

路徑壓縮優化後,并查集的時間複雜度已經比較低了,絕大多數不相交集合的合并查詢問題都能夠解決。然而,對于某些時間卡得很緊的題目,我們還可以進一步優化。

三、按秩合并

有些人可能有一個誤解,以為路徑壓縮優化後,并查集始終都是一個菊花圖(隻有兩層的樹的俗稱)。但其實,由于路徑壓縮隻在查詢時進行,也隻壓縮一條路徑,是以并查集最終的結構仍然可能是比較複雜的。例如,現在我們有一棵較複雜的樹需要與一個單元素的集合合并:

【算法】算法學習筆記: 并查集【轉載】

假如這時我們要merge(7,8),如果我們可以選擇的話,是把7的父節點設為8好,還是把8的父節點設為7好呢?

當然是後者。因為如果把7的父節點設為8,會使樹的深度(樹中最長鍊的長度)加深,原來的樹中每個元素到根節點的距離都變長了,之後我們尋找根節點的路徑也就會相應變長。雖然我們有路徑壓縮,但路徑壓縮也是會消耗時間的。而把8的父節點設為7,則不會有這個問題,因為它沒有影響到不相關的節點。

【算法】算法學習筆記: 并查集【轉載】

這啟發我們:我們應該把簡單的樹往複雜的樹上合并,而不是相反。因為這樣合并後,到根節點距離變長的節點個數比較少。

我們用一個數組rank[]記錄每個根節點對應的樹的深度(如果不是根節點,其rank相當于以它作為根節點的子樹的深度)。一開始,把所有元素的rank(秩)設為1。合并時比較兩個根節點,把rank較小者往較大者上合并。路徑壓縮和按秩合并如果一起使用,時間複雜度接近 O ( n ) O(n) O(n) ,但是很可能會破壞rank的準确性。

值得注意的是,按秩合并會帶來額外的空間複雜度,可能被一些卡空間的毒瘤題卡掉。

初始化(按秩合并)

inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
           

合并(按秩合并)

inline void merge(int i, int j)
{
    int x = find(i), y = find(j);    //先找到兩個根節點
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;                   //如果深度相同且根節點不同,則新的根節點的深度+1
}
           

為什麼深度相同,新的根節點深度要+1?如下圖,我們有兩個深度均為2的樹,現在要merge(2,5):

【算法】算法學習筆記: 并查集【轉載】

這裡把2的父節點設為5,或者把5的父節點設為2,其實沒有太大差別。我們選擇前者,于是變成這樣:

【算法】算法學習筆記: 并查集【轉載】

顯然樹的深度增加了1。另一種合并方式同樣會讓樹的深度+1。

四、并查集的應用

我們先給出親戚問題的AC代碼:

#include <cstdio>
#define MAXN 5005
int fa[MAXN], rank[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
}
int main()
{
    int n, m, p, x, y;
    scanf("%d%d%d", &n, &m, &p);
    init(n);
    for (int i = 0; i < m; ++i)
    {
        scanf("%d%d", &x, &y);
        merge(x, y);
    }
    for (int i = 0; i < p; ++i)
    {
        scanf("%d%d", &x, &y);
        printf("%s\n", find(x) == find(y) ? "Yes" : "No");
    }
    return 0;
}
           

接下來我們來看一道NOIP提高組原題:

(NOIP提高組2017年D2T1 洛谷P3958 奶酪)

題目描述

現有一塊大奶酪,它的高度為 h h h ,它的長度和寬度我們可以認為是無限大的,奶酪中間有許多半徑相同的球形空洞。我們可以在這塊奶酪中建立空間坐标系,在坐标系中, 奶酪的下表面為 z = 0 z=0 z=0 ,奶酪的上表面為 z = h z=h z=h 。

現在,奶酪的下表面有一隻小老鼠 Jerry,它知道奶酪中所有空洞的球心所在的坐标。如果兩個空洞相切或是相交,則 Jerry 可以從其中一個空洞跑到另一個空洞,特别地,如果一個空洞與下表面相切或是相交,Jerry 則可以從奶酪下表面跑進空洞;如果一個空洞與上表面相切或是相交,Jerry 則可以從空洞跑到奶酪上表面。

位于奶酪下表面的 Jerry 想知道,在 不破壞奶酪 的情況下,能否利用已有的空洞跑到奶酪的上表面去?

空間内兩點 P 1 ( x 1 , y 1 , z 1 ) P_1(x_1, y_1,z_1) P1​(x1​,y1​,z1​)、 P 2 ( x 2 , y 2 , z 2 ) P_2(x_2, y_2,z_2) P2​(x2​,y2​,z2​)、 的距離公式如下:

d i s t ( P 1 , P 2 ) = ( x 1 − x 2 ) 2 + ( y 1 − y 2 ) 2 + ( z 1 − z 2 ) 2 dist(P_1, P_2) = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2+(z_1-z_2)^2} dist(P1​,P2​)=(x1​−x2​)2+(y1​−y2​)2+(z1​−z2​)2

輸入格式

每個輸入檔案包含多組資料。

的第一行,包含一個正整數 T T T ,代表該輸入檔案中所含的資料組數。

接下來是 T T T組資料,每組資料的格式如下: 第一行包含三個正整數 n , h n, h n,h 和 r r r ,兩個數之間以一個空格分開,分别代表奶酪中空 洞的數量,奶酪的高度和空洞的半徑。

接下來的 n n n行,每行包含三個整數 x , y , z x,y,z x,y,z,兩個數之間以一個空格分開,表示空 洞球心坐标為 ( x , y , z ) (x,y,z) (x,y,z) 。

輸出格式

T T T行,分别對應 T T T組資料的答案,如果在第 i i i組資料中,Jerry 能從下表面跑到上表面,則輸出Yes,如果不能,則輸出No(均不包含引号)。

大家看出這道題和并查集的關系了嗎?

【算法】算法學習筆記: 并查集【轉載】

這是二維版本,題目中的三維版本是類似的

大家看看上面這張圖,是不是看出一些門道了?我們把所有空洞劃分為若幹個集合,一旦兩個空洞相交或相切,就把它們放到同一個集合中。

我們還可以劃出2個特殊元素,分别表示底部和頂部,如果一個空洞與底部接觸,則把它與表示底部的元素放在同一個集合中,頂部同理。最後,隻需要看頂部和底部是不是在同一個集合中即可。這完全可以通過并查集實作。來看代碼:

#include <cstdio>
#include <cstring>
#define MAXN 1005
typedef long long ll;
int fa[MAXN], rank[MAXN];
ll X[MAXN], Y[MAXN], Z[MAXN];
inline bool next_to(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2, ll r)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2) <= 4 * r * r;
    //判斷兩個空洞是否相交或相切
}
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        fa[i] = i;
        rank[i] = 1;
    }
}
int find(int x)
{
    return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j)
{
    int x = find(i), y = find(j);
    if (rank[x] <= rank[y])
        fa[x] = y;
    else
        fa[y] = x;
    if (rank[x] == rank[y] && x != y)
        rank[y]++;
}
int main()
{
    int T, n, h;
    ll r;
    scanf("%d", &T);
    for (int I = 0; I < T; ++I)
    {
        memset(X, 0, sizeof(X));
        memset(Y, 0, sizeof(Y));
        memset(Z, 0, sizeof(Z));
        scanf("%d%d%lld", &n, &h, &r);
        init(n);
        fa[1001] = 1001; //用1001代表底部
        fa[1002] = 1002; //用1002代表頂部
        for (int i = 1; i <= n; ++i)
            scanf("%lld%lld%lld", X + i, Y + i, Z + i);
        for (int i = 1; i <= n; ++i)
        {
            if (Z[i] <= r)
                merge(i, 1001); //與底部接觸的空洞與底部合并
            if (Z[i] + r >= h)
                merge(i, 1002); //與頂部接觸的空洞與頂部合并
        }
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i + 1; j <= n; ++j)
            {
                if (next_to(X[i], Y[i], Z[i], X[j], Y[j], Z[j], r))
                    merge(i, j); //周遊所有空洞,合并相交或相切的球
            }
        }
        printf("%s\n", find(1001) == find(1002) ? "Yes" : "No");
    }
    return 0;
}
           

因為資料範圍的原因,這裡要開一個long long。

并查集的應用還有很多,例如最小生成樹的Kruskal算法等。這裡就不細講了。總而言之,凡是涉及到元素的分組管理問題,都可以考慮使用并查集進行維護。

繼續閱讀