讀完本文，你可以去力扣拿下如下題目：

130.被圍繞的區域

990.等式方程的可滿足性

-----------

希望你已經讀了這篇題解 Union-Find 演算法詳解

上篇文章很多讀者對於 Union-Find 演算法的應用表示很感興趣，這篇文章就拿幾道 LeetCode 題目來講講這個演算法的巧妙用法。

首先，複習一下，Union-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;        }    }        /* 將 p 和 q 連通 */    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--;    }    /* 判斷 p 和 q 是否互相連通 */    public boolean connected(int p, int q) {        int rootP = find(p);        int rootQ = find(q);        // 處於同一棵樹上的節點，相互連通        return rootP == rootQ;    }    /* 返回節點 x 的根節點 */    private int find(int x) {        while (parent[x] != x) {            // 進行路徑壓縮            parent[x] = parent[parent[x]];            x = parent[x];        }        return x;    }        public int count() {        return count;    }}

演算法的關鍵點有 3 個：

1、用 parent 陣列記錄每個節點的父節點，相當於指向父節點的指標，所以 parent 陣列內實際儲存著一個森林（若干棵多叉樹）。

2、用 size 陣列記錄著每棵樹的重量，目的是讓 union 後樹依然擁有平衡性，而不會退化成連結串列，影響操作效率。

3、在 find 函式中進行路徑壓縮，保證任意樹的高度保持在常數，使得 union 和 connected API 時間複雜度為 O(1)。

有的讀者問，既然有了路徑壓縮，size 陣列的重量平衡還需要嗎？這個問題很有意思，因為路徑壓縮保證了樹高為常數（不超過 3），那麼樹就算不平衡，高度也是常數，基本沒什麼影響。

我認為，論時間複雜度的話，確實，不需要重量平衡也是 O(1)。但是如果加上 size 陣列輔助，效率還是略微高一些，比如下面這種情況：

如果帶有重量平衡最佳化，一定會得到情況一，而不帶重量最佳化，可能出現情況二。高度為 3 時才會觸發路徑壓縮那個 while 迴圈，所以情況一根本不會觸發路徑壓縮，而情況二會多執行很多次路徑壓縮，將第三層節點壓縮到第二層。

也就是說，去掉重量平衡，雖然對於單個的 find 函式呼叫，時間複雜度依然是 O(1)，但是對於 API 呼叫的整個過程，效率會有一定的下降。當然，好處就是減少了一些空間，不過對於 Big O 表示法來說，時空複雜度都沒變。

下面言歸正傳，來看看這個演算法有什麼實際應用。

一、DFS 的替代方案

很多使用 DFS 深度優先演算法解決的問題，也可以用 Union-Find 演算法解決。

比如第 130 題，被圍繞的區域：給你一個 M×N 的二維矩陣，其中包含字元 X 和 O，讓你找到矩陣中四面被 X 圍住的 O，並且把它們替換成 X。

void solve(char[][] board);

注意哦，必須是四面被圍的 O 才能被換成 X，也就是說邊角上的 O 一定不會被圍，進一步，與邊角上的 O 相連的 O 也不會被 X 圍四面，也不會被替換。

PS：這讓我想起小時候玩的棋類遊戲「黑白棋」，只要你用兩個棋子把對方的棋子夾在中間，對方的子就被替換成你的子。可見，佔據四角的棋子是無敵的，與其相連的邊棋子也是無敵的（無法被夾掉）。

解決這個問題的傳統方法也不困難，先用 for 迴圈遍歷棋盤的四邊，用 DFS 演算法把那些與邊界相連的 O 換成一個特殊字元，比如 #；然後再遍歷整個棋盤，把剩下的 O 換成 X，把 # 恢復成 O。這樣就能完成題目的要求，時間複雜度 O(MN)。

這個問題也可以用 Union-Find 演算法解決，雖然實現複雜一些，甚至效率也略低，但這是使用 Union-Find 演算法的通用思想，值得一學。

你可以把那些不需要被替換的 O 看成一個擁有獨門絕技的門派，它們有一個共同祖師爺叫 dummy，這些 O 和 dummy 互相連通，而那些需要被替換的 O 與 dummy 不連通。

這就是 Union-Find 的核心思路，明白這個圖，就很容易看懂程式碼了。

首先要解決的是，根據我們的實現，Union-Find 底層用的是一維陣列，建構函式需要傳入這個陣列的大小，而題目給的是一個二維棋盤。

這個很簡單，二維座標 (x,y) 可以轉換成 x * n + y 這個數（m 是棋盤的行數，n 是棋盤的列數）。敲黑板，這是將二維座標對映到一維的常用技巧。

其次，我們之前描述的「祖師爺」是虛構的，需要給他老人家留個位置。索引 [0.. m*n-1] 都是棋盤內座標的一維對映，那就讓這個虛擬的 dummy 節點佔據索引 m * n 好了。

void solve(char[][] board) {    if (board.length == 0) return;    int m = board.length;    int n = board[0].length;    // 給 dummy 留一個額外位置    UF uf = new UF(m * n + 1);    int dummy = m * n;    // 將首列和末列的 O 與 dummy 連通    for (int i = 0; i < m; i++) {        if (board[i][0] == 'O')            uf.union(i * n, dummy);        if (board[i][n - 1] == 'O')            uf.union(i * n + n - 1, dummy);    }    // 將首行和末行的 O 與 dummy 連通    for (int j = 0; j < n; j++) {        if (board[0][j] == 'O')            uf.union(j, dummy);        if (board[m - 1][j] == 'O')            uf.union(n * (m - 1) + j, dummy);    }    // 方向陣列 d 是上下左右搜尋的常用手法    int[][] d = new int[][]{{1,0}, {0,1}, {0,-1}, {-1,0}};    for (int i = 1; i < m - 1; i++)         for (int j = 1; j < n - 1; j++)             if (board[i][j] == 'O')                // 將此 O 與上下左右的 O 連通                for (int k = 0; k < 4; k++) {                    int x = i + d[k][0];                    int y = j + d[k][1];                    if (board[x][y] == 'O')                        uf.union(x * n + y, i * n + j);                }    // 所有不和 dummy 連通的 O，都要被替換    for (int i = 1; i < m - 1; i++)         for (int j = 1; j < n - 1; j++)             if (!uf.connected(dummy, i * n + j))                board[i][j] = 'X';}

這段程式碼很長，其實就是剛才的思路實現，只有和邊界 O 相連的 O 才具有和 dummy 的連通性，他們不會被替換。

說實話，Union-Find 演算法解決這個簡單的問題有點殺雞用牛刀，它可以解決更復雜，更具有技巧性的問題，主要思路是適時增加虛擬節點，想辦法讓元素「分門別類」，建立動態連通關係。

二、判定合法等式

這個問題用 Union-Find 演算法就顯得十分優美了。題目是這樣：

給你一個數組 equations，裝著若干字串表示的算式。每個算式 equations[i] 長度都是 4，而且只有這兩種情況：a==b 或者 a!=b，其中 a,b 可以是任意小寫字母。你寫一個演算法，如果 equations 中所有算式都不會互相沖突，返回 true，否則返回 false。

比如說，輸入 ["a==b","b!=c","c==a"]，演算法返回 false，因為這三個算式不可能同時正確。

再比如，輸入 ["c==c","b==d","x!=z"]，演算法返回 true，因為這三個算式並不會造成邏輯衝突。

我們前文說過，動態連通性其實就是一種等價關係，具有「自反性」「傳遞性」和「對稱性」，其實 == 關係也是一種等價關係，具有這些性質。所以這個問題用 Union-Find 演算法就很自然。

核心思想是，將 equations 中的算式根據 == 和 != 分成兩部分，先處理 == 算式，使得他們透過相等關係各自勾結成門派；然後處理 != 算式，檢查不等關係是否破壞了相等關係的連通性。

boolean equationsPossible(String[] equations) {    // 26 個英文字母    UF uf = new UF(26);    // 先讓相等的字母形成連通分量    for (String eq : equations) {        if (eq.charAt(1) == '=') {            char x = eq.charAt(0);            char y = eq.charAt(3);            uf.union(x - 'a', y - 'a');        }    }    // 檢查不等關係是否打破相等關係的連通性    for (String eq : equations) {        if (eq.charAt(1) == '!') {            char x = eq.charAt(0);            char y = eq.charAt(3);            // 如果相等關係成立，就是邏輯衝突            if (uf.connected(x - 'a', y - 'a'))                return false;        }    }    return true;}

至此，這道判斷算式合法性的問題就解決了，藉助 Union-Find 演算法，是不是很簡單呢？

三、簡單總結

使用 Union-Find 演算法，主要是如何把原問題轉化成圖的動態連通性問題。對於算式合法性問題，可以直接利用等價關係，對於棋盤包圍問題，則是利用一個虛擬節點，營造出動態連通特性。

另外，將二維陣列對映到一維陣列，利用方向陣列 d 來簡化程式碼量，都是在寫演算法時常用的一些小技巧，如果沒見過可以注意一下。

很多更復雜的 DFS 演算法問題，都可以利用 Union-Find 演算法更漂亮的解決。LeetCode 上 Union-Find 相關的問題也就二十多道，有興趣的讀者可以去做一做。