前言

并查集（Disjoint-set） 的代碼非常簡潔找爱，但是功能卻很強(qiáng)大枯芬。
關(guān)于并查集宵荒，這里有一篇文章超有愛的并查集~，講得非常好苔悦，但是只使用了并查集兩個(gè)主要優(yōu)化中的"路徑壓縮"優(yōu)化轩褐，并且我覺得很多情況下采用遞歸的寫法要比采用循環(huán)的寫法要易懂很多。本文將使用C++實(shí)現(xiàn)并查集并使用“按秩合并”和”路徑壓縮“優(yōu)化并查集间坐。我們先大概了解什么是并查集灾挨。

什么是并查集（Disjoint-set）

對于一個(gè)集合S={a₁, a₂, ..., a_n-1, a_n}，我們還可以對集合S進(jìn)一步劃分: S₁,S₂,...,S_m-1,S_m竹宋，我們希望能夠快速確定S中的兩兩元素是否屬于S的同一子集劳澄。
舉個(gè)栗子，S={0蜈七，1, 2, 3, 4, 5, 6}秒拔，如果我們按照一定的規(guī)則對集合S進(jìn)行劃分,假設(shè)劃分后為S₁={1, 2, 4}, S₂={3, 6}，S₃={0, 5}飒硅，任意給定兩個(gè)元素砂缩，我們?nèi)绾未_定它們是否屬于同一子集作谚？某些合并子集后，又如何確定兩兩關(guān)系庵芭？基于此類問題便出現(xiàn)了并查集這種數(shù)據(jù)結(jié)構(gòu)妹懒。
并查集有兩個(gè)基本操作：

• Find: 查找元素所屬子集
• Union：合并兩個(gè)子集為一個(gè)新的集合

并查集的基本結(jié)構(gòu)

我們可以使用樹這種數(shù)據(jù)結(jié)構(gòu)來表示集合，不同的樹就是不同的集合双吆，并查集中包含了多棵樹眨唬，表示并查集中不同的子集，樹的集合是森林好乐，所以并查集屬于森林匾竿。
若集合S={0, 1, 2, 3, 4, 5, 6}，最初每一個(gè)元素都是一棵樹蔚万。

圖1

對于Union操作岭妖，我們只需要將兩棵樹合并，例如合并0反璃、1昵慌、2得到S₁={0, 1, 2},合并3和4得到S₂={3, 4}

圖2

對于Find操作，我們只需要返回該元素所在樹的根節(jié)點(diǎn)版扩。所以废离，如果我們想要比較判斷1和2是否在一個(gè)集合，只需要通過Find(1)和Find(2)返回各自的根節(jié)點(diǎn)比較是否相等便可礁芦。已知樹中的一個(gè)節(jié)點(diǎn)蜻韭，找到其根節(jié)點(diǎn)的時(shí)間復(fù)雜度為O(D)，D為節(jié)點(diǎn)的深度柿扣。
我們可以使用數(shù)組來表示樹肖方，數(shù)組下標(biāo)表示樹的一個(gè)節(jié)點(diǎn)，該下表所對應(yīng)的值表示樹的父節(jié)點(diǎn)未状。例如P[i]表示元素i的父節(jié)點(diǎn)俯画。對于圖2中的集合，我們可以存儲在下面的數(shù)組中（第二行為數(shù)組下標(biāo)）

對于樹的根節(jié)點(diǎn)司草，我們規(guī)定其元素值為其本身（即父節(jié)點(diǎn)為自己）艰垂。

C++實(shí)現(xiàn)一

我們使用一個(gè)parent數(shù)組存儲樹，先實(shí)現(xiàn)未經(jīng)優(yōu)化的版本埋虹。
對于Find操作猜憎，代碼非常簡單

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

該代碼比較元素x的父節(jié)點(diǎn)parent[x]是否等于x自身，如果是便說明找到了根節(jié)點(diǎn)（根節(jié)點(diǎn)的父節(jié)點(diǎn)是自身）搔课，直接返回胰柑；否則，把x的父節(jié)點(diǎn)parent[x]傳入find，直到找到根節(jié)點(diǎn)柬讨。
下面是union操作

void to_union(int x1, int x2) 
{
    int p1 = find(x1);
    int p2 = find(x2);
    parent[p1] = p2;
}

傳入兩個(gè)元素崩瓤，分別找到根節(jié)點(diǎn)，使根節(jié)點(diǎn)p1的父節(jié)點(diǎn)為p2踩官，即將p1為根節(jié)點(diǎn)的這棵樹合并到p2為根節(jié)點(diǎn)的樹上却桶。
下面是完整代碼：

#include <vector>
class DisjSet
{
private:
    std::vector<int> parent;

public:
    DisjSet(int max_size) : parent(std::vector<int>(max_size))
    {
        // 初始化每一個(gè)元素的根節(jié)點(diǎn)都為自身
        for (int i = 0; i < max_size; ++i)
            parent[i] = i;
    }
    int find(int x)
    {
        return parent[x] == x ? x : find(parent[x]);
    }
    void to_union(int x1, int x2)
    {
        parent[find(x1)] = find(x2);
    }
    // 判斷兩個(gè)元素是否屬于同一個(gè)集合
    bool is_same(int e1, int e2)
    {
        return find(e1) == find(e2);
    }
};

剛學(xué)并查集的時(shí)候看到這里都快哭了，這代碼也簡潔了吧:joy:蔗牡。
上面的實(shí)現(xiàn)肾扰，可以看出每一次Find操作的時(shí)間復(fù)雜度為O(H)，H為樹的高度蛋逾，由于我們沒有對樹做特殊處理，所以樹的不斷合并可能會使樹嚴(yán)重不平衡窗悯，最壞情況每個(gè)節(jié)點(diǎn)都只有一個(gè)子節(jié)點(diǎn)区匣，如下圖3（第一個(gè)點(diǎn)為根節(jié)點(diǎn)）

圖3

此時(shí)Find操作的時(shí)間復(fù)雜度為O(n)，這顯然不是我們想要的蒋院。下面引入兩個(gè)優(yōu)化的方法亏钩。

并查集的優(yōu)化

方法一：

"按秩合并"。實(shí)際上就是在合并兩棵樹時(shí)欺旧，將高度較小的樹合并到高度較大的樹上姑丑。這里我們使用“秩”(rank)代替高度，秩表示高度的上界辞友，通常情況我們令只有一個(gè)節(jié)點(diǎn)的樹的秩為0栅哀，嚴(yán)格來說，rank + 1才是高度的上界称龙；兩棵秩分別為r₁留拾、r₂的樹合并，如果秩不相等鲫尊，我們將秩小的樹合并到秩大的樹上痴柔，這樣就能保證新樹秩不大于原來的任意一棵樹。如果r₁與r₂相等疫向，兩棵樹任意合并咳蔚，并令新樹的秩為r₁ + 1。

方法二：

“路徑壓縮”搔驼。在執(zhí)行Find的過程中谈火，將路徑上的所有節(jié)點(diǎn)都直接連接到根節(jié)點(diǎn)上。

圖4

同時(shí)使用這兩種方法的平均時(shí)間復(fù)雜度為匙奴，是的反函數(shù)堆巧，是阿克曼函數(shù)，增長率非常之高，所以在n非常大的時(shí)候谍肤，依然小于5啦租。下面是采用"按秩合并"與“路徑壓縮”兩中優(yōu)化算法的實(shí)現(xiàn)。

C++實(shí)現(xiàn)二（優(yōu)化版）

#include <vector>
class DisjSet
{
  private:
    std::vector<int> parent;
    std::vector<int> rank; // 秩

  public:
    DisjSet(int max_size) : parent(std::vector<int>(max_size)),
                            rank(std::vector<int>(max_size, 0))
    {
        for (int i = 0; i < max_size; ++i)
            parent[i] = i;
    }
    int find(int x)
    {
        return x == parent[x] ? x : (parent[x] = find(parent[x]));
    }
    void to_union(int x1, int x2)
    {
        int f1 = find(x1);
        int f2 = find(x2);
        if (rank[f1] > rank[f2])
            parent[f2] = f1;
        else
        {
            parent[f1] = f2;
            if (rank[f1] == rank[f2])
                ++rank[f2];
        }
    }
    bool is_same(int e1, int e2)
    {
        return find(e1) == find(e2);
    }
};

總結(jié)

時(shí)間復(fù)雜度

采用“路徑壓縮”與“按秩合并”優(yōu)化的并查集每個(gè)操作的平均時(shí)間復(fù)雜度為荒揣，是的反函數(shù)篷角，在n非常大的時(shí)候，依然小于5系任。

空間復(fù)雜度

恳蹲，n為元素的數(shù)量

參考資料

1. 并查集---維基百科
2. 數(shù)據(jù)結(jié)構(gòu)與算法分析-C語言描述 第二版
3. 算法導(dǎo)論（原書第3版）

本作品采用知識共享署名-非商業(yè)性使用-禁止演繹 4.0 國際許可協(xié)議進(jìn)行許可。轉(zhuǎn)載請注明: 作者staneyffer俩滥，首發(fā)于我的博客嘉蕾，原文鏈接: https://chengfy.com/post/9