高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-1

“并查集”這部分知識(shí)點(diǎn)講得最清楚的是《算法》（第 4 版），本篇“并查集”的介紹是我看這本書第 1.5 節(jié)的學(xué)習(xí)筆記。

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-2

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-3

什么是“并查集”

為什么叫并查集呢锈玉？因?yàn)樵谶@個(gè)數(shù)據(jù)結(jié)構(gòu)中悦冀，“并”和“查”是經(jīng)常使用的兩個(gè)操作未辆∏酆荆“并”是把兩個(gè)元素合并在一起汇四，僅表示“這兩個(gè)元素之間有連接”，“查”就是查詢兩個(gè)元素是不是連接在一起踢涌。因此通孽，如果我們?cè)谝恍﹫?chǎng)景下，只需要查詢兩個(gè)事物之間是否有聯(lián)系睁壁，“并查集”就是一個(gè)不錯(cuò)的選擇背苦。例如：“查詢兩個(gè)人是不是好友關(guān)系”（請(qǐng)看下面的練習(xí)1）∨嗣鳎“查詢從一個(gè)地方到另一個(gè)地方是否能走通”（請(qǐng)看下面的練習(xí)2）行剂。

并查集主要用于解決連通問題，即抽象概念中結(jié)點(diǎn)和結(jié)點(diǎn)是否連接钳降。而路徑問題厚宰，不僅僅要考慮連通問題，我們還要往往還需要求出最短路徑遂填，這不是并查集做的事情固阁。因此并查集問題能做的事情比路徑問題少，它更專注于（1）判斷連接狀態(tài)（查）（2）改變連接狀態(tài)（并）城菊。

具體說來备燃，并查集的代碼需要實(shí)現(xiàn)以下的 3 個(gè)功能：

1、 find(p)：查找元素 p 所對(duì)應(yīng)的集合凌唬，

說明：這個(gè)函數(shù)一般不對(duì)外開放并齐，僅作為私有方法被下面兩個(gè)函數(shù)調(diào)用。

2客税、 union(p, q)：合并元素 p 和元素 q 所在的集合况褪。
3、 connected(p, q)：查詢?cè)?p 和元素 q 是不是在同一個(gè)集合中更耻。

因此测垛，我們的并查集其實(shí)就是要實(shí)現(xiàn)下面的這個(gè)接口：

Java 代碼：

public interface IUnionFind {

    // 并查集的版本名稱，由開發(fā)者指定
    String versionName();

    // p (0 到 N-1)所在的分量的標(biāo)識(shí)符
    int find(int p);

    // 如果 p 和 q 存在于同一分量中則返回 true
    boolean connected(int p, int q);

    // 在 p 與 q 之間添加一條連接
    void union(int p, int q);

}

特別注意：馬上我們將會(huì)看到秧均，其實(shí)“并查集”是一棵樹食侮，這棵樹與以往我們構(gòu)建樹的方式大不相同，“并查集”構(gòu)建的樹從“孩子結(jié)點(diǎn)”指向“父親結(jié)點(diǎn)”目胡。這一點(diǎn)是“并查集”的特色锯七。

并查集第 1 版：quick-find

我們首先解決并查集用什么數(shù)據(jù)結(jié)構(gòu)來表示呢？其實(shí)使用數(shù)組就可以了誉己，這個(gè)數(shù)組我們可以起一個(gè)名字叫做 id 眉尸。初始化的情況下，每一個(gè)元素的 id 都是不一樣的韵丑。如果是一樣的盆赤，表示是屬于同一個(gè)集合內(nèi)的元素。

基于 id 的 quick-find 的思路：設(shè)置 id 數(shù)組犁珠，數(shù)組的每個(gè)元素是分量標(biāo)識(shí)袱蜡。

從 quick-find 這個(gè)名字上看丝蹭，我們這一版的實(shí)現(xiàn)，對(duì)于 find(int p) 這個(gè)操作來說是高效的戒劫，但對(duì)于 union(int p, int q) 這個(gè)操作是低效的，因?yàn)樾枰闅v整個(gè)并查集婆廊。find(int p) 這個(gè)操作的時(shí)間復(fù)雜度是 迅细，而 union(int p, int q) 這個(gè)操作的時(shí)間復(fù)雜度是 ，要全部遍歷并查集中的元素淘邻，把其中一個(gè)分量標(biāo)識(shí)的所有結(jié)點(diǎn)的編號(hào)更改為另一個(gè)一個(gè)分量標(biāo)識(shí)茵典。

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-4

例如上面的表格中，如果我們要將第 1 行的 0 和 1 執(zhí)行 union(int p, int q) 操作宾舅，有兩種方式：第 1 種方式：把第 1 行的 0统阿，2，4筹我，6扶平，8 的 id 全改成 1；第 2 種方式：把第 1 行的 1蔬蕊，3结澄，5，7岸夯，9 的 id 全改成 0麻献。我們可以看到，union(int p, int q) 的操作完全是和問題的規(guī)模成正比的猜扮，所以 quick-find 下的 union(int p, int q) 操作時(shí)間復(fù)雜度是 勉吻。

Java 代碼：

public class UnionFind1 implements IUnionFind {

    private int[] id; // 分量 id

    private int count; // 連通分量的數(shù)量

    public UnionFind1(int n) {
        this.count = n;
        // 初始化分量 id 數(shù)組
        id = new int[n];
        for (int i = 0; i < n; i++) {
            id[i] = i;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 1 個(gè)版本，基于 id 數(shù)組旅赢，quick-find";
    }

    // 以常數(shù)時(shí)間復(fù)雜度齿桃，返回分量的標(biāo)識(shí)符，與并查集的規(guī)模是無關(guān)的煮盼，這一步很快
    // 因此我們稱這個(gè)版本的并查集是 quick-find
    @Override
    public int find(int p) {
        return id[p];
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    // 因?yàn)樾枰闅v數(shù)組中的全部元素源譬，所以這個(gè)版本其實(shí)效率并不高
    @Override
    public void union(int p, int q) {
        int pid = find(p);
        int qid = find(q);

        // 如果 p 和 q 已經(jīng)在相同的分量之中，則什么都不做
        if (pid == qid) {
            return;
        }

        // 將 p 的分量重新命名為 q 的名稱
        for (int i = 0; i < id.length; i++) {
            if (find(i) == pid) {
                id[i] = qid;
            }
        }
        // 每次 union 以后孕似，連通分量減 1
        count--;
    }
}

使用 id 數(shù)組在進(jìn)行 union(int p, int q) 的時(shí)候踩娘，要遍歷整個(gè)數(shù)組中的結(jié)點(diǎn)，這種方式效率不高，因此养渴，我們換一種思路：由于 union(int p, int q) 慢雷绢，所以我們就想辦法讓 union(int p, int q) 快起來。

并查集第 2 版：quick-union

我們不再使用 id 數(shù)組理卑，而使用 parent 數(shù)組翘紊，parent 數(shù)組的定義是：parent[i] 表示索引為 i 的結(jié)點(diǎn)的父親結(jié)點(diǎn)的索引，在這個(gè)定義下藐唠，根結(jié)點(diǎn)的父親結(jié)點(diǎn)是自己帆疟。

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-5

此時(shí)查詢結(jié)點(diǎn) p 和結(jié)點(diǎn) q 相連這件事情，就是我們分別追溯 parent[p] 和 parent[q] （可以看到這樣的過程很像在一棵樹中的操作）宇立，查詢到 parent[p] 和 parent[q] 的根結(jié)點(diǎn)踪宠，如果根結(jié)點(diǎn)相同，那么它們就同屬于一個(gè)集合妈嘹。

這樣看來柳琢，find(int p) 好像費(fèi)點(diǎn)勁，這也是我們接來下的幾個(gè)并查集優(yōu)化的方向润脸，都是在 find(int p) 上做文章柬脸，但這保證了 union(int p, int q) 很快，我們只需把其中一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)指向另一個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)（而誰的父結(jié)點(diǎn)指向誰的根結(jié)點(diǎn)毙驯，也是我們后幾版并查集優(yōu)化的方向）倒堕，就完成了 union(int p, int q) 的操作。此時(shí) union(int p, int q) 的操作只須要一行代碼：

Java 代碼：

parent[pRoot] = qRoot;

初始化的時(shí)候爆价，我們將每個(gè)元素都指向自己涩馆，此時(shí)表示這 個(gè)結(jié)點(diǎn)互相之間沒有連接關(guān)系。如下表所示：

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-6

上面的數(shù)組表示的并查集如下允坚。

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-7

Java 代碼：

public class UnionFind2 implements IUnionFind {

    private int[] parent; // 第 i 個(gè)元素存放它的父元素的索引

    private int count; // 連通分量的數(shù)量

    public UnionFind2(int n) {
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 2 個(gè)版本，基于 parent 數(shù)組埂软，quick-union";
    }

    @Override
    public int find(int p) {
        // 跟隨鏈接找到根結(jié)點(diǎn)
        while (parent[p] != p) { // 只要不是根結(jié)點(diǎn)
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p); // 將 p 歸并與之相同的分量中
        int qRoot = find(q); // 將 q 歸并與之相同的分量中

        // 如果 p 和 q 已經(jīng)在相同的分量之中锈遥，則什么都不做
        if (pRoot == qRoot) {
            return;
        }
        // 如果 parent[qRoot] = pRoot; 也是可以的，即將其中一個(gè)結(jié)點(diǎn)指向另一個(gè)結(jié)點(diǎn)
        parent[pRoot] = qRoot;
        // 每次 union 以后，連通分量減 1
        count--;
    }
}

并查集第 3 版：quick-union 基于 size 的優(yōu)化

我們發(fā)現(xiàn) union 4,9 與 union 9,4 其實(shí)是一樣的所灸，也就是把誰的根指向誰的根丽惶，這一點(diǎn)從正確性上來說是無關(guān)緊要的，但是對(duì)于 find 的時(shí)間復(fù)雜度就會(huì)有影響爬立。為此钾唬，我們做如下優(yōu)化。

在合并之前做判斷侠驯，具體做法是抡秆，計(jì)算每一個(gè)結(jié)點(diǎn)有多少個(gè)元素直接或者間接地以它為根，我們應(yīng)該將集合元素少的那結(jié)點(diǎn)的根指向集合元素多的那個(gè)結(jié)點(diǎn)的根吟策。這樣儒士，形成的樹就會(huì)更高概率地形成一棵層數(shù)較低的樹。

為此踊挠，我們?cè)僖胍粋€(gè) size 數(shù)組乍桂，size[i] 的定義是：以第 i 個(gè)結(jié)點(diǎn)為根的集合的元素的個(gè)數(shù)冲杀。

在初始化的時(shí)候 size[i] = 1效床，find 和 isConnected 操作中我們都不須要去維護(hù) size 這個(gè)數(shù)組，唯獨(dú)在 unionElements 的時(shí)候权谁，我們才要維護(hù) size 數(shù)組的定義剩檀。

Java 代碼：

// union-find 算法的實(shí)現(xiàn)（加權(quán) quick-union 算法）
public class UnionFind3 implements IUnionFind {

    private int[] parent; // 第 i 個(gè)元素存放它的父元素的索引

    private int count; // 連通分量的數(shù)量

    private int[] size; // 以當(dāng)前索引為根的樹所包含的元素的總數(shù)

    public UnionFind3(int n) {
        this.count = n;
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            // 初始化時(shí)，所有的元素只包含它自己旺芽，只有一個(gè)元素沪猴，所以 size[i] = 1
            size[i] = 1;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 3 個(gè)版本，基于 parent 數(shù)組采章，quick-union运嗜，基于 size";
    }

    // 返回索引為 p 的元素的根結(jié)點(diǎn)的索引
    @Override
    public int find(int p) {
        // 跟隨鏈接找到根結(jié)點(diǎn)
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        return pRoot == qRoot;
    }

    @Override
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        // 這一步是與第 2 版不同的地方，我們不是沒有根據(jù)地把一個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)的父結(jié)點(diǎn)指向另一個(gè)結(jié)點(diǎn)的根結(jié)點(diǎn)
        // 而是將小樹的根結(jié)點(diǎn)連接到大樹的根結(jié)點(diǎn)
        if (size[pRoot] > size[qRoot]) {
            parent[qRoot] = pRoot;
            size[pRoot] += size[qRoot];
        } else {
            parent[pRoot] = qRoot;
            size[qRoot] += size[pRoot];
        }
        // 每次 union 以后悯舟，連通分量減 1
        count--;
    }
}

并查集第 4 版：quick-union 基于 rank 的優(yōu)化

使用 size 來決定將哪個(gè)結(jié)點(diǎn)的根指向另一個(gè)結(jié)點(diǎn)的根担租，其實(shí)并不太合理，但并不能說不正確抵怎，因?yàn)檎l的根指向誰的根奋救，其實(shí)都沒有錯(cuò)，下面就是一個(gè)特殊的情況反惕。

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-8

因?yàn)槲覀兛偸瞧谕@棵樹的高度比較低尝艘，在這種情況下，我們?cè)?find 的時(shí)候姿染，就能通過很少的步數(shù)來找到根結(jié)點(diǎn)背亥，進(jìn)而提高 find 的效率。為此，我們引入 rank 數(shù)組隘梨，其定義是： rank[i] 表示以第 i 個(gè)元素為根的樹的高度程癌。

Java 代碼：

public class UnionFind4 implements IUnionFind {

    private int[] parent;

    private int count;

    // 以索引為 i 的元素為根結(jié)點(diǎn)的樹的深度（最深的那個(gè)深度）
    private int[] rank;

    public UnionFind4(int n) {
        this.count = n;
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            // 初始化時(shí)，所有的元素只包含它自己轴猎，只有一個(gè)元素嵌莉，所以 rank[i] = 1
            rank[i] = 1;
        }
    }

    @Override
    public String versionName() {
        return "并查集的第 4 個(gè)版本，基于 parent 數(shù)組捻脖，quick-union锐峭，基于 rank";
    }

    // 返回索引為 p 的元素的根結(jié)點(diǎn)
    @Override
    public int find(int p) {
        // 跟隨鏈接找到根結(jié)點(diǎn)
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public boolean connected(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        return pRoot == qRoot;
    }


    @Override
    public void union(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        // 這一步是與第 3 版不同的地方
        if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = pRoot;
        } else if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        } else {
            parent[qRoot] = pRoot;
            rank[pRoot]++;
        }
        // 每次 union 以后，連通分量減 1
        count--;
    }
}

并查集第 5 版：quick-union 基于路徑壓縮的非遞歸實(shí)現(xiàn)

那么什么是路徑壓縮 path Compression可婶？以上我們都是針對(duì)于 union 操作的優(yōu)化沿癞，其實(shí)我們?cè)?find 的時(shí)候，就可以對(duì)一棵樹進(jìn)行整理矛渴，讓它的高度變低椎扬，這一點(diǎn)是基于并查集的一個(gè)特性：只要它們是連在一起的，其實(shí)誰指向誰具温，并不重要蚕涤，所以我們?cè)诮酉聛淼挠懻撝锌吹降牟⒉榧谋硎緢D，它們是等價(jià)的铣猩，即它們表示的都是同一個(gè)并查集揖铜。

路徑壓縮 path Compression 的思路：在 find 的時(shí)候一次又一次的整理，將并查集構(gòu)造（整理）成一個(gè)與之等價(jià)的并查集达皿，使得后續(xù)的每一次 find 這樣的操作路徑最短天吓。

假設(shè)一個(gè)最極端的并查集的圖表示如下：

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-9

我們開始找 的父親結(jié)點(diǎn)， 的父親結(jié)點(diǎn)不是 峦椰，說明不是根結(jié)點(diǎn)龄寞，此時(shí)，我們嘗試 步一跳汤功，將 的父親結(jié)點(diǎn)“改成”父親結(jié)點(diǎn)的父親結(jié)點(diǎn)物邑，于是得到一個(gè)等價(jià)的并查集：

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-10

下面我們?cè)摽疾煸? 了， 的父親結(jié)點(diǎn)是 冤竹， 不是根結(jié)點(diǎn)拂封，所以我們繼續(xù)兩步一跳，把 的父親結(jié)點(diǎn)設(shè)置成它的父親結(jié)點(diǎn)的父親結(jié)點(diǎn)鹦蠕，于是又得到一個(gè)等價(jià)的并查集：

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-11

此時(shí)冒签，整棵樹的高度就在一次 find 的過程中被壓縮了。這里有一個(gè)疑問：即使我們?cè)谧詈笾徊钜徊降那闆r下钟病，我們跳兩步萧恕，也不會(huì)出現(xiàn)無效的索引刚梭。其實(shí)，一步一跳票唆，兩步一跳朴读，甚至三步一跳都沒有關(guān)系。

畫圖畫了這么多走趋，代碼實(shí)現(xiàn)只有一行：parent[p] = parent[parent[p]]; 編寫的時(shí)候要注意這行代碼添加的位置衅金，畫一個(gè)示意圖，想想這個(gè)路徑壓縮的過程簿煌，就不難寫出氮唯。

Java 代碼：

public int find(int p) {
    // 在 find 的時(shí)候執(zhí)行路徑壓縮
    while (p != parent[p]) {
        // 編寫這句代碼的時(shí)候可能會(huì)覺得有點(diǎn)繞，
        // 畫一個(gè)示意圖姨伟，就能很直觀地寫出正確的邏輯
        // 兩步一跳完成路徑壓縮
        parent[p] = parent[parent[p]];
        p = parent[p];
    }
    return p;
}

根據(jù)上面的圖惩琉，我們通過 find 操作執(zhí)行路徑壓縮，最終形成的并查集如下：

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-12

并查集第 6 版：quick-union 基于路徑壓縮的遞歸實(shí)現(xiàn)

代碼的實(shí)現(xiàn)的理解有一些繞夺荒。這一版我們實(shí)現(xiàn)壓縮更徹底的路徑壓縮瞒渠。其實(shí)我們不看上面的分析，我們想象路徑壓縮的目的是什么技扼，就是讓我們的并查集表示的樹結(jié)構(gòu)層數(shù)更低伍玖，那么最優(yōu)的情況應(yīng)該是下面這樣，把一棵樹壓縮成 層淮摔，所有的結(jié)點(diǎn)都指向一個(gè)根私沮，這才是把一個(gè)并查集壓縮到最徹底的情況始赎。

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-13

那么和橙，代碼又應(yīng)該如何實(shí)現(xiàn)呢？我們需要使用遞歸的思想造垛。這一版代碼的實(shí)現(xiàn)難點(diǎn)就在于：應(yīng)該定義 find(p) 返回的是 p 這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)魔招。

Java 代碼：

/**
 * 返回索引為 p 的元素的根結(jié)點(diǎn)
 * 理解這個(gè)方法的關(guān)鍵點(diǎn)：我們就是要把這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)指向根結(jié)點(diǎn)，
 * 既然父親結(jié)點(diǎn)不是根結(jié)點(diǎn)五辽，我們就繼續(xù)拿父親結(jié)點(diǎn)找根結(jié)點(diǎn)
 * 一致遞歸找下去办斑，
 * 最后返回的時(shí)候，寫 parent[p] 是可以的
 * 寫 parent[parent[p]] 也是沒有問題的
 *
 * @param p
 * @return
 */
public int find(int p) {
    // 在 find 的時(shí)候執(zhí)行路徑壓縮
    assert p >= 0 && p < count;
    // 注意：這里是 if 不是 while杆逗，否則就變成循環(huán)
    if (p != parent[p]) {
        // 這一行代碼的邏輯要想想清楚
        // 只要不是根結(jié)點(diǎn)
        // 就把父親結(jié)點(diǎn)指向父親結(jié)點(diǎn)的父親結(jié)點(diǎn)
        parent[p] = find(parent[p]);
    }
    return parent[p];
}

最后乡翅，我們來比較一下基于路徑壓縮的兩種方法。

高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集-14

并查集能夠很好地幫助我們解決網(wǎng)絡(luò)中兩個(gè)結(jié)點(diǎn)是否連接的問題罪郊。但是蠕蚜，對(duì)于網(wǎng)絡(luò)中的兩個(gè)結(jié)點(diǎn)的路徑，最短路徑的問題悔橄，我們就要使用圖來解決靶累。

關(guān)于路徑壓縮的思考

寫到這里腺毫，我們發(fā)現(xiàn)在路徑壓縮的過程中，我們之前引入的輔助合并的數(shù)組挣柬，不管是 rank 還是 size潮酒，它們的定義都不準(zhǔn)確了，因?yàn)槲覀冊(cè)诼窂綁嚎s的過程中沒有對(duì)它們的定義進(jìn)行維護(hù)邪蛔。這一點(diǎn)其實(shí)并不影響我們的算法的正確性急黎，我們不去維護(hù) rank 數(shù)組和 size 數(shù)組的定義，是因?yàn)榈?1 點(diǎn)：難于實(shí)現(xiàn)侧到，第 2 點(diǎn)： rank 數(shù)組還是 size 數(shù)組的當(dāng)前實(shí)現(xiàn)仍然可以作為一個(gè)參考值叁熔，比起隨機(jī)的做法要更有意義一些。

其實(shí)寫到這里床牧，數(shù)組 rank 還是數(shù)組 size 的意義都不太重要了荣回，我們只須要在 find 的時(shí)候，做好路徑壓縮戈咳，把孩子結(jié)點(diǎn)指向父親結(jié)點(diǎn)即可心软。

并查集第 7 版：易于理解的路徑壓縮算法

這個(gè)版本的并查集在 find 的時(shí)候做得更徹底，把在“查找”過程中沿途經(jīng)過的“結(jié)點(diǎn)”直接指向了最終的根結(jié)點(diǎn)著蛙。

Python 代碼：

class UnionFind7:
    def __init__(self, n):
        self.parent = [i for i in range(n)]
        self.count = n

    def find(self, p):
        """
        查找元素 p 根節(jié)點(diǎn)的編號(hào)
        :param p:
        :return:
        """
        assert 0 <= p < self.count
        root = p
        
        while root != self.parent[root]:
            root = self.parent[root]
        
        # 此時(shí) root 就是大 boss
        # 下面這一步就是最直接的路徑壓縮：
        # 把沿途查找過的結(jié)點(diǎn)都指向 root
        while p != self.parent[p]:
            temp = self.parent[p]
            self.parent[p] = root
            p = temp
        return root

    def is_connected(self, p, q):
        """
        查詢?cè)?p 和 q 是否屬于同一個(gè)集合
        有共同的父親删铃，就表示它們屬于同一個(gè)集合
        :param p:
        :param q:
        :return:
        """
        return self.find(p) == self.find(q)

    def union(self, p, q):
        """
        合并元素 p 和元素 q 所屬于的集合
        O(n)復(fù)雜度
        :param p:
        :param q:
        :return:
        """

        p_id = self.find(p)
        q_id = self.find(q)
        if p_id == q_id:
            return
        # 任意指向即可
        self.parent[p_id] = q_id

下面，我們來看 LeetCode 上關(guān)于“并查集”的三個(gè)問題踏堡。

例題

例題1：LeetCode 第 547 題：朋友圈

傳送門：英文網(wǎng)址：547. Friend Circles猎唁，中文網(wǎng)址：547. 朋友圈。

班上有 N 名學(xué)生顷蟆。其中有些人是朋友诫隅，有些則不是。他們的友誼具有是傳遞性帐偎。如果已知 A 是 B 的朋友逐纬，B 是 C 的朋友，那么我們可以認(rèn)為 A 也是 C 的朋友削樊。所謂的朋友圈豁生，是指所有朋友的集合。

給定一個(gè) N * N 的矩陣 M漫贞，表示班級(jí)中學(xué)生之間的朋友關(guān)系甸箱。如果M[i][j] = 1，表示已知第 i 個(gè)和 j 個(gè)學(xué)生互為朋友關(guān)系迅脐，否則為不知道芍殖。你必須輸出所有學(xué)生中的已知的朋友圈總數(shù)。

示例 1:

輸入: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
輸出: 2 
說明：已知學(xué)生0和學(xué)生1互為朋友仪际，他們?cè)谝粋€(gè)朋友圈围小。
第2個(gè)學(xué)生自己在一個(gè)朋友圈昵骤。所以返回2。

示例 2:

輸入: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
輸出: 1
說明：已知學(xué)生0和學(xué)生1互為朋友肯适，學(xué)生1和學(xué)生2互為朋友变秦，所以學(xué)生0和學(xué)生2也是朋友，所以他們?nèi)齻€(gè)在一個(gè)朋友圈框舔，返回1蹦玫。

注意：

1. N 在[1,200]的范圍內(nèi)。
2. 對(duì)于所有學(xué)生刘绣，有M[i][i] = 1樱溉。
3. 如果有M[i][j] = 1，則有M[j][i] = 1纬凤。

思路1：好友關(guān)系是雙向關(guān)系福贞，因此題目中給出的矩陣其實(shí)是一個(gè)鄰接矩陣，所以問題就轉(zhuǎn)化為求圖中有幾個(gè)連通分量的問題了停士。

思路2：我們還可以用并查集來解決它挖帘。由于是對(duì)陣矩陣，我們其實(shí)只要看這個(gè)矩陣的下三角形部分就可以了恋技。又因?yàn)樽约嚎隙ㄊ亲约旱暮糜涯匆ǎ赃€可以不看對(duì)角線，蜻底。

Python 代碼：

class Solution(object):

    def findCircleNum(self, M):
        """
        :type M: List[List[int]]
        :rtype: int
        """
        class UnionFind:
            def __init__(self, n):
                self.parent = [i for i in range(n)]

            def find(self, p):
                root = p
                # 只要不是最上層的那個(gè)結(jié)點(diǎn)骄崩，就不停向上找
                while root != self.parent[root]:
                    root = self.parent[root]
                # 此時(shí) root 就是大 boss
                # 接下來把 p 到 root 沿途所有的結(jié)點(diǎn)都指向 root
                while p != self.parent[p]:
                    temp = self.parent[p]
                    self.parent[p] = root
                    p = temp
                return root

            def is_connected(self, p, q):
                return self.find(p) == self.find(q)

            def union(self, p, q):
                p_id = self.find(p)
                q_id = self.find(q)
                if p_id == q_id:
                    return
                self.parent[p_id] = q_id

        m = len(M)
        union_find_set = UnionFind(m)
        # 只看下三角矩陣(不包括對(duì)角線)
        for i in range(m):
            for j in range(i):
                if M[i][j] == 1:
                    union_find_set.union(j, i)
        counter = 0
        # print(union_find_set.parent)
        # 自己的父親是自己的話，這個(gè)結(jié)點(diǎn)就是根結(jié)點(diǎn)薄辅，是老大要拂，是 boss
        # boss 的特點(diǎn)就是，他上面沒有人长搀，例如：李彥宏宇弛、馬云
        # 數(shù)一數(shù)有幾個(gè)老大鸡典，就有幾個(gè)朋友圈
        for index, parent in enumerate(union_find_set.parent):
            if index == parent:
                counter += 1
        return counter


if __name__ == '__main__':
    M = [[1, 1, 0],
         [1, 1, 0],
         [0, 0, 1]]

    solution = Solution()
    result = solution.findCircleNum(M)
    print(result)

例題2：LeetCode 第 130 題：被圍繞的區(qū)域

傳送門：英文網(wǎng)址：200. Number of Islands源请，中文網(wǎng)址：200. 島嶼的個(gè)數(shù)。

給定一個(gè)二維的矩陣彻况，包含 'X' 和 'O'（字母 O）谁尸。

找到所有被 'X' 圍繞的區(qū)域，并將這些區(qū)域里所有的 'O' 用 'X' 填充纽甘。

示例:

X X X X
X O O X
X X O X
X O X X

運(yùn)行你的函數(shù)后良蛮，矩陣變?yōu)椋?/p>

X X X X
X X X X
X X X X
X O X X

解釋:

被圍繞的區(qū)間不會(huì)存在于邊界上，換句話說悍赢，任何邊界上的 'O' 都不會(huì)被填充為 'X'决瞳。 任何不在邊界上货徙，或不與邊界上的 'O' 相連的 'O' 最終都會(huì)被填充為 'X'。如果兩個(gè)元素在水平或垂直方向相鄰皮胡，則稱它們是“相連”的痴颊。

分析：其實(shí)就是將不與邊上的 'O' 相連的 'O' 改成 'X'，可以使用并查集完成屡贺。

Python 代碼1：一開始的寫法蠢棱，不太好理解。

class Solution:
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """

        # 使用并查集
        class UnionFind:
            def __init__(self, n):
                self.parent = [i for i in range(n)]

            def find(self, p):
                root = p
                while root != self.parent[root]:
                    root = self.parent[root]
                while p != self.parent[p]:
                    temp = self.parent[p]
                    self.parent[p] = root
                    p = temp
                return root

            def is_connected(self, p, q):
                return self.find(p) == self.find(q)

            def union(self, p, q):
                p_id = self.find(p)
                q_id = self.find(q)
                if p_id == q_id:
                    return
                self.parent[p_id] = q_id

        # 一開始是常規(guī)的代碼
        m = len(board)
        if m == 0:
            return
        n = len(board[0])

        def get_index(x, y):
            return x * n + y

        directions = [(-1, 0), (0, -1), (1, 0), (0, 1)]
        # 這里多留了一個(gè)位置甩栈，表示與邊上的 'O' 相連
        uf = UnionFind(m * n + 1)
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    # 把所有不被 'X' 包圍的 'O' 放在同一個(gè)集合里
                    if i == 0 or j == 0 or i == m - 1 or j == n - 1:
                        uf.union(get_index(i, j), m * n)
                    else:
                        # 向 4 個(gè)方向找泻仙，只用看 4 個(gè)方向，不要和回溯算法混淆了
                        # 只要都是 'O' 量没，才有必要合并
                        for direction in directions:
                            new_i = i + direction[0]
                            new_j = j + direction[1]
                            if board[new_i][new_j] == 'O':
                                uf.union(get_index(i, j), get_index(new_i, new_j))

        # 最后玉转，才內(nèi)圈里，只要是 'O'殴蹄，且不與邊上的 'O' 連接冤吨，都改成 'X' 即可  
        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if board[i][j] == 'O' and not uf.is_connected(get_index(i, j), m * n):
                    board[i][j] = 'X'

這個(gè)版本寫出來，感覺思路不是很清晰饶套，于是漩蟆，我又寫了一版。

Python 代碼2：其實(shí)并查集的寫法容易受 floorfill 的影響妓蛮，用并查集的時(shí)候怠李，其實(shí)只用每一行的右邊和下面都看一下，只針對(duì)“O”蛤克，能合并就合并一下捺癞。

class Solution:
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """

        # 使用并查集
        class UnionFind:
            def __init__(self, n):
                self.parent = [i for i in range(n)]

            def find(self, p):
                root = p
                while root != self.parent[root]:
                    root = self.parent[root]
                while p != self.parent[p]:
                    temp = self.parent[p]
                    self.parent[p] = root
                    p = temp
                return root

            def is_connected(self, p, q):
                return self.find(p) == self.find(q)

            def union(self, p, q):
                p_id = self.find(p)
                q_id = self.find(q)
                if p_id == q_id:
                    return
                self.parent[p_id] = q_id

        # 一開始是常規(guī)的代碼
        m = len(board)
        if m == 0:
            return
        n = len(board[0])

        def get_index(x, y):
            return x * n + y

        dummy_node = m * n

        uf = UnionFind(m * n + 1)

        # 先把四條邊上的 "O" 全部連起來
        for row_index in range(m):
            if board[row_index][0] == 'O':
                uf.union(get_index(row_index, 0), dummy_node)
            if board[row_index][n - 1] == 'O':
                uf.union(get_index(row_index, n - 1), dummy_node)

        for col_index in range(n):
            if board[0][col_index] == 'O':
                uf.union(get_index(0, col_index), dummy_node)
            if board[m - 1][col_index] == 'O':
                uf.union(get_index(m - 1, col_index), dummy_node)

        directions = [(1, 0), (0, 1)]
        for i in range(m):
            for j in range(n):
                if board[i][j] == 'O':
                    # 只向 2 個(gè)方向找，只用看 2 個(gè)方向构挤，不要和回溯算法混淆了
                    for direction in directions:
                        new_i = i + direction[0]
                        new_j = j + direction[1]
                        if new_i < m and new_j < n and board[new_i][new_j] == 'O':
                            uf.union(get_index(i, j), get_index(new_i, new_j))

        for i in range(1, m - 1):
            for j in range(1, n - 1):
                if board[i][j] == 'O' and not uf.is_connected(get_index(i, j), m * n):
                    board[i][j] = 'X'

練習(xí)3：LeetCode 第 200 題：島嶼的個(gè)數(shù)

給定一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格髓介，計(jì)算島嶼的數(shù)量。一個(gè)島被水包圍筋现，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的唐础。你可以假設(shè)網(wǎng)格的四個(gè)邊均被水包圍。

示例 1:

輸入:
11110
11010
11000
00000

輸出: 1

示例 2:

輸入:
11000
11000
00100
00011

輸出: 3

思路1：floorfill矾飞，可以在這里看到這個(gè)思路的代碼一膨。

思路2：使用并查集，把所有的“0”都合并到一個(gè)虛擬的結(jié)點(diǎn)上洒沦，然后掃描整個(gè)二維矩陣豹绪。

Python 代碼：

class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """

        class UnionFind:
            def __init__(self, n):
                self.parent = [i for i in range(n)]

            def find(self, p):
                root = p
                while root != self.parent[root]:
                    root = self.parent[root]
                while p != self.parent[p]:
                    temp = self.parent[p]
                    self.parent[p] = root
                    p = temp
                return root

            def is_connected(self, p, q):
                return self.find(p) == self.find(q)

            def union(self, p, q):
                p_id = self.find(p)
                q_id = self.find(q)
                if p_id == q_id:
                    return
                self.parent[p_id] = q_id

        row = len(grid)
        if row == 0:
            return 0
        col = len(grid[0])

        def get_index(x, y):
            return x * col + y

        directions = [(1, 0), (0, 1)]
        # 多開一個(gè)空間，把 "0" 都?xì)w到這個(gè)虛擬的老大上
        dummy_node = row * col

        uf = UnionFind(dummy_node + 1)
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '0':
                    uf.union(get_index(i, j), dummy_node)
                if grid[i][j] == '1':
                    # 向下向右如果都是 "1" 就要合并一下
                    for direction in directions:
                        new_x = i + direction[0]
                        new_y = j + direction[1]
                        if new_x < row and new_y < col and grid[new_x][new_y] == '1':
                            uf.union(get_index(i, j), get_index(new_x, new_y))
        # 因?yàn)橐欢ㄒ獪p掉 "0" 的區(qū)域申眼，因此起始值是 -1
        res = -1
        for index, parent in enumerate(uf.parent):
            if parent == index:
                res += 1
        return res

最后附上我以前學(xué)習(xí)并查集的時(shí)候?qū)懙墓P記瞒津，傳送門：高級(jí)數(shù)據(jù)結(jié)構(gòu)：并查集（Java 實(shí)現(xiàn)）蝉衣。

本文源代碼

Python：代碼文件夾，Java：代碼文件夾巷蚪。

（本節(jié)完）