-----------

今天講講 Union-Find 演算法，也就是常說的並查集演算法，主要是解決圖論中「動態連通性」問題的。名詞很高階，其實特別好理解，等會解釋，另外這個演算法的應用都非常有趣。

說起這個 Union-Find，應該算是我的「啟蒙演算法」了，因為《演算法4》的開頭就介紹了這款演算法，可是把我秀翻了，感覺好精妙啊！後來刷了 LeetCode，並查集相關的演算法題目都非常有意思，而且《演算法4》給的解法竟然還可以進一步最佳化，只要加一個微小的修改就可以把時間複雜度降到 O(1)。

廢話不多說，直接上乾貨，先解釋一下什麼叫動態連通性吧。

一、問題介紹

簡單說，動態連通性其實可以抽象成給一幅圖連線。比如下面這幅圖，總共有 10 個節點，他們互不相連，分別用 0~9 標記：

現在我們的 Union-Find 演算法主要需要實現這兩個 API：

class UF {    /* 將 p 和 q 連線 */    public void union(int p, int q);    /* 判斷 p 和 q 是否連通 */    public boolean connected(int p, int q);    /* 返回圖中有多少個連通分量 */    public int count();}

這裡所說的「連通」是一種等價關係，也就是說具有如下三個性質：

1、自反性：節點p和p是連通的。

2、對稱性：如果節點p和q連通，那麼q和p也連通。

3、傳遞性：如果節點p和q連通，q和r連通，那麼p和r也連通。

比如說之前那幅圖，0～9 任意兩個不同的點都不連通，呼叫connected都會返回 false，連通分量為 10 個。

如果現在呼叫union(0, 1)，那麼 0 和 1 被連通，連通分量降為 9 個。

再呼叫union(1, 2)，這時 0,1,2 都被連通，呼叫connected(0, 2)也會返回 true，連通分量變為 8 個。

這樣，你應該大概明白什麼是動態連通性了，Union-Find 演算法的關鍵就在於union和connected函式的效率。那麼用什麼模型來表示這幅圖的連通狀態呢？用什麼資料結構來實現程式碼呢？

二、基本思路

注意我剛才把「模型」和具體的「資料結構」分開說，這麼做是有原因的。因為我們使用森林（若干棵樹）來表示圖的動態連通性，用陣列來具體實現這個森林。

怎麼用森林來表示連通性呢？我們設定樹的每個節點有一個指標指向其父節點，如果是根節點的話，這個指標指向自己。比如說剛才那幅 10 個節點的圖，一開始的時候沒有相互連通，就是這樣：

class UF {    // 記錄連通分量    private int count;    // 節點 x 的節點是 parent[x]    private int[] parent;    /* 建構函式，n 為圖的節點總數 */    public UF(int n) {        // 一開始互不連通        this.count = n;        // 父節點指標初始指向自己        parent = new int[n];        for (int i = 0; i < n; i++)            parent[i] = i;    }    /* 其他函式 */}

如果某兩個節點被連通，則讓其中的（任意）一個節點的根節點接到另一個節點的根節點上：

public void union(int p, int q) {    int rootP = find(p);    int rootQ = find(q);    if (rootP == rootQ)        return;    // 將兩棵樹合併為一棵    parent[rootP] = rootQ;    // parent[rootQ] = rootP 也一樣    count--; // 兩個分量合二為一}/* 返回某個節點 x 的根節點 */private int find(int x) {    // 根節點的 parent[x] == x    while (parent[x] != x)        x = parent[x];    return x;}​/* 返回當前的連通分量個數 */public int count() {     return count;}

這樣，如果節點p和q連通的話，它們一定擁有相同的根節點：

public boolean connected(int p, int q) {    int rootP = find(p);    int rootQ = find(q);    return rootP == rootQ;}

至此，Union-Find 演算法就基本完成了。是不是很神奇？竟然可以這樣使用陣列來模擬出一個森林，如此巧妙的解決這個比較複雜的問題！

那麼這個演算法的複雜度是多少呢？我們發現，主要 APIconnected和union中的複雜度都是find函式造成的，所以說它們的複雜度和find一樣。

find主要功能就是從某個節點向上遍歷到樹根，其時間複雜度就是樹的高度。我們可能習慣性地認為樹的高度就是logN，但這並不一定。logN的高度只存在於平衡二叉樹，對於一般的樹可能出現極端不平衡的情況，使得「樹」幾乎退化成「連結串列」，樹的高度最壞情況下可能變成N。

所以說上面這種解法，find,union,connected的時間複雜度都是 O(N)。這個複雜度很不理想的，你想圖論解決的都是諸如社交網路這樣資料規模巨大的問題，對於union和connected的呼叫非常頻繁，每次呼叫需要線性時間完全不可忍受。

問題的關鍵在於，如何想辦法避免樹的不平衡呢？只需要略施小計即可。

三、平衡性最佳化

我們要知道哪種情況下可能出現不平衡現象，關鍵在於union過程：

public void union(int p, int q) {    int rootP = find(p);    int rootQ = find(q);    if (rootP == rootQ)        return;    // 將兩棵樹合併為一棵    parent[rootP] = rootQ;    // parent[rootQ] = rootP 也可以    count--; 

我們一開始就是簡單粗暴的把p所在的樹接到q所在的樹的根節點下面，那麼這裡就可能出現「頭重腳輕」的不平衡狀況，比如下面這種局面：

長此以往，樹可能生長得很不平衡。我們其實是希望，小一些的樹接到大一些的樹下面，這樣就能避免頭重腳輕，更平衡一些。解決方法是額外使用一個size陣列，記錄每棵樹包含的節點數，我們不妨稱為「重量」：

class UF {    private int count;    private int[] parent;    // 新增一個數組記錄樹的“重量”    private int[] size;​    public UF(int n) {        this.count = n;        parent = new int[n];        // 最初每棵樹只有一個節點        // 重量應該初始化 1        size = new int[n];        for (int i = 0; i < n; i++) {            parent[i] = i;            size[i] = 1;        }    }    /* 其他函式 */}

比如說size[3] = 5表示，以節點3為根的那棵樹，總共有5個節點。這樣我們可以修改一下union方法：

public void union(int p, int q) {    int rootP = find(p);    int rootQ = find(q);    if (rootP == rootQ)        return;        // 小樹接到大樹下面，較平衡    if (size[rootP] > size[rootQ]) {        parent[rootQ] = rootP;        size[rootP] += size[rootQ];    } else {        parent[rootP] = rootQ;        size[rootQ] += size[rootP];    }    count--;}

這樣，透過比較樹的重量，就可以保證樹的生長相對平衡，樹的高度大致在logN這個數量級，極大提升執行效率。

此時，find,union,connected的時間複雜度都下降為 O(logN)，即便資料規模上億，所需時間也非常少。

四、路徑壓縮

這步最佳化特別簡單，所以非常巧妙。我們能不能進一步壓縮每棵樹的高度，使樹高始終保持為常數？

這樣find就能以 O(1) 的時間找到某一節點的根節點，相應的，connected和union複雜度都下降為 O(1)。

要做到這一點，非常簡單，只需要在find中加一行程式碼：

private int find(int x) {    while (parent[x] != x) {        // 進行路徑壓縮        parent[x] = parent[parent[x]];        x = parent[x];    }    return x;}

這個操作有點匪夷所思，看個 GIF 就明白它的作用了（為清晰起見，這棵樹比較極端）：

可見，呼叫find函式每次向樹根遍歷的同時，順手將樹高縮短了，最終所有樹高都不會超過 3（union的時候樹高可能達到 3）。

PS：讀者可能會問，這個 GIF 圖的find過程完成之後，樹高恰好等於 3 了，但是如果更高的樹，壓縮後高度依然會大於 3 呀？不能這麼想。這個 GIF 的情景是我編出來方便大家理解路徑壓縮的，但是實際中，每次find都會進行路徑壓縮，所以樹本來就不可能增長到這麼高，你的這種擔心應該是多餘的。

五、最後總結

我們先來看一下完整程式碼：

class UF {    // 連通分量個數    private int count;    // 儲存一棵樹    private int[] parent;    // 記錄樹的“重量”    private int[] size;    public UF(int n) {        this.count = n;        parent = new int[n];        size = new int[n];        for (int i = 0; i < n; i++) {            parent[i] = i;            size[i] = 1;        }    }        public void union(int p, int q) {        int rootP = find(p);        int rootQ = find(q);        if (rootP == rootQ)            return;                // 小樹接到大樹下面，較平衡        if (size[rootP] > size[rootQ]) {            parent[rootQ] = rootP;            size[rootP] += size[rootQ];        } else {            parent[rootP] = rootQ;            size[rootQ] += size[rootP];        }        count--;    }    public boolean connected(int p, int q) {        int rootP = find(p);        int rootQ = find(q);        return rootP == rootQ;    }    private int find(int x) {        while (parent[x] != x) {            // 進行路徑壓縮            parent[x] = parent[parent[x]];            x = parent[x];        }        return x;    }    public int count() {        return count;    }}

Union-Find 演算法的複雜度可以這樣分析：建構函式初始化資料結構需要 O(N) 的時間和空間複雜度；連通兩個節點union、判斷兩個節點的連通性connected、計算連通分量count所需的時間複雜度均為 O(1)。

    public int findCircleNum(int[][] M) {        int n = M.length;        UF uf = new UF(n);        for (int i = 0; i < n; i++) {            for (int j = 0; j < i; j++) {                if (M[i][j] == 1)                    uf.union(i, j);            }        }                return uf.count();    }