讀完本文，你可以去力扣拿下如下題目：
-----------
希望你已經(jīng)讀了這篇題解 Union-Find 算法詳解
上篇文章很多讀者對(duì)于 Union-Find 算法的應(yīng)用表示很感興趣，這篇文章就拿幾道 LeetCode 題目來講講這個(gè)算法的巧妙用法。
首先，復(fù)習(xí)一下，Union-Find 算法解決的是圖的動(dòng)態(tài)連通性問題，這個(gè)算法本身不難，能不能應(yīng)用出來主要是看你抽象問題的能力，是否能夠把原始問題抽象成一個(gè)有關(guān)圖論的問題。
先復(fù)習(xí)一下上篇文章寫的算法代碼，回答讀者提出的幾個(gè)問題：
class UF {
// 記錄連通分量個(gè)數(shù)
private int count;
// 存儲(chǔ)若干棵樹
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);
// 處于同一棵樹上的節(jié)點(diǎn)，相互連通
return rootP == rootQ;
}
/* 返回節(jié)點(diǎn) x 的根節(jié)點(diǎn) */
private int find(int x) {
while (parent[x] != x) {
// 進(jìn)行路徑壓縮
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int count() {
return count;
}
}
算法的關(guān)鍵點(diǎn)有 3 個(gè)：
1、用 parent 數(shù)組記錄每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)，相當(dāng)于指向父節(jié)點(diǎn)的指針，所以 parent 數(shù)組內(nèi)實(shí)際存儲(chǔ)著一個(gè)森林（若干棵多叉樹）。
2、用 size 數(shù)組記錄著每棵樹的重量，目的是讓 union 后樹依然擁有平衡性，而不會(huì)退化成鏈表，影響操作效率。
3、在 find 函數(shù)中進(jìn)行路徑壓縮，保證任意樹的高度保持在常數(shù)，使得 union 和 connected API 時(shí)間復(fù)雜度為 O(1)。
有的讀者問，既然有了路徑壓縮，size 數(shù)組的重量平衡還需要嗎？這個(gè)問題很有意思，因?yàn)槁窂綁嚎s保證了樹高為常數(shù)（不超過 3），那么樹就算不平衡，高度也是常數(shù)，基本沒什么影響。
我認(rèn)為，論時(shí)間復(fù)雜度的話，確實(shí)，不需要重量平衡也是 O(1)。但是如果加上 size 數(shù)組輔助，效率還是略微高一些，比如下面這種情況：
如果帶有重量平衡優(yōu)化，一定會(huì)得到情況一，而不帶重量?jī)?yōu)化，可能出現(xiàn)情況二。高度為 3 時(shí)才會(huì)觸發(fā)路徑壓縮那個(gè) while 循環(huán)，所以情況一根本不會(huì)觸發(fā)路徑壓縮，而情況二會(huì)多執(zhí)行很多次路徑壓縮，將第三層節(jié)點(diǎn)壓縮到第二層。
也就是說，去掉重量平衡，雖然對(duì)于單個(gè)的 find 函數(shù)調(diào)用，時(shí)間復(fù)雜度依然是 O(1)，但是對(duì)于 API 調(diào)用的整個(gè)過程，效率會(huì)有一定的下降。當(dāng)然，好處就是減少了一些空間，不過對(duì)于 Big O 表示法來說，時(shí)空復(fù)雜度都沒變。
下面言歸正傳，來看看這個(gè)算法有什么實(shí)際應(yīng)用。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
一、DFS 的替代方案
很多使用 DFS 深度優(yōu)先算法解決的問題，也可以用 Union-Find 算法解決。
比如第 130 題，被圍繞的區(qū)域：給你一個(gè) M×N 的二維矩陣，其中包含字符 X 和 O，讓你找到矩陣中四面被 X 圍住的 O，并且把它們替換成 X。
void solve(char[][] board);
注意哦，必須是四面被圍的 O 才能被換成 X，也就是說邊角上的 O 一定不會(huì)被圍，進(jìn)一步，與邊角上的 O 相連的 O 也不會(huì)被 X 圍四面，也不會(huì)被替換。
PS：這讓我想起小時(shí)候玩的棋類游戲「黑白棋」，只要你用兩個(gè)棋子把對(duì)方的棋子夾在中間，對(duì)方的子就被替換成你的子?？梢?，占據(jù)四角的棋子是無敵的，與其相連的邊棋子也是無敵的（無法被夾掉）。
解決這個(gè)問題的傳統(tǒng)方法也不困難，先用 for 循環(huán)遍歷棋盤的四邊，用 DFS 算法把那些與邊界相連的 O 換成一個(gè)特殊字符，比如 #；然后再遍歷整個(gè)棋盤，把剩下的 O 換成 X，把 # 恢復(fù)成 O。這樣就能完成題目的要求，時(shí)間復(fù)雜度 O(MN)。
這個(gè)問題也可以用 Union-Find 算法解決，雖然實(shí)現(xiàn)復(fù)雜一些，甚至效率也略低，但這是使用 Union-Find 算法的通用思想，值得一學(xué)。
你可以把那些不需要被替換的 O 看成一個(gè)擁有獨(dú)門絕技的門派，它們有一個(gè)共同祖師爺叫 dummy，這些 O 和 dummy 互相連通，而那些需要被替換的 O 與 dummy 不連通。
這就是 Union-Find 的核心思路，明白這個(gè)圖，就很容易看懂代碼了。
首先要解決的是，根據(jù)我們的實(shí)現(xiàn)，Union-Find 底層用的是一維數(shù)組，構(gòu)造函數(shù)需要傳入這個(gè)數(shù)組的大小，而題目給的是一個(gè)二維棋盤。
這個(gè)很簡(jiǎn)單，二維坐標(biāo) (x,y) 可以轉(zhuǎn)換成 x * n + y 這個(gè)數(shù)（m 是棋盤的行數(shù)，n 是棋盤的列數(shù)）。敲黑板，這是將二維坐標(biāo)映射到一維的常用技巧。
其次，我們之前描述的「祖師爺」是虛構(gòu)的，需要給他老人家留個(gè)位置。索引 [0.. m*n-1] 都是棋盤內(nèi)坐標(biāo)的一維映射，那就讓這個(gè)虛擬的 dummy 節(jié)點(diǎn)占據(jù)索引 m * n 好了。
void solve(char[][] board) {
if (board.length == 0) return;
int m = board.length;
int n = board[0].length;
// 給 dummy 留一個(gè)額外位置
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);
}
// 方向數(shù)組 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';
}
這段代碼很長(zhǎng)，其實(shí)就是剛才的思路實(shí)現(xiàn)，只有和邊界 O 相連的 O 才具有和 dummy 的連通性，他們不會(huì)被替換。
說實(shí)話，Union-Find 算法解決這個(gè)簡(jiǎn)單的問題有點(diǎn)殺雞用牛刀，它可以解決更復(fù)雜，更具有技巧性的問題，主要思路是適時(shí)增加虛擬節(jié)點(diǎn)，想辦法讓元素「分門別類」，建立動(dòng)態(tài)連通關(guān)系。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
二、判定合法等式
這個(gè)問題用 Union-Find 算法就顯得十分優(yōu)美了。題目是這樣：
給你一個(gè)數(shù)組 equations，裝著若干字符串表示的算式。每個(gè)算式 equations[i] 長(zhǎng)度都是 4，而且只有這兩種情況：a==b 或者 a!=b，其中 a,b 可以是任意小寫字母。你寫一個(gè)算法，如果 equations 中所有算式都不會(huì)互相沖突，返回 true，否則返回 false。
比如說，輸入 ["a==b","b!=c","c==a"]，算法返回 false，因?yàn)檫@三個(gè)算式不可能同時(shí)正確。
再比如，輸入 ["c==c","b==d","x!=z"]，算法返回 true，因?yàn)檫@三個(gè)算式并不會(huì)造成邏輯沖突。
我們前文說過，動(dòng)態(tài)連通性其實(shí)就是一種等價(jià)關(guān)系，具有「自反性」「?jìng)鬟f性」和「對(duì)稱性」，其實(shí) == 關(guān)系也是一種等價(jià)關(guān)系，具有這些性質(zhì)。所以這個(gè)問題用 Union-Find 算法就很自然。
核心思想是，將 equations 中的算式根據(jù) == 和 != 分成兩部分，先處理 == 算式，使得他們通過相等關(guān)系各自勾結(jié)成門派；然后處理 != 算式，檢查不等關(guān)系是否破壞了相等關(guān)系的連通性。
boolean equationsPossible(String[] equations) {
// 26 個(gè)英文字母
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');
}
}
// 檢查不等關(guān)系是否打破相等關(guān)系的連通性
for (String eq : equations) {
if (eq.charAt(1) == '!') {
char x = eq.charAt(0);
char y = eq.charAt(3);
// 如果相等關(guān)系成立，就是邏輯沖突
if (uf.connected(x - 'a', y - 'a'))
return false;
}
}
return true;
}
至此，這道判斷算式合法性的問題就解決了，借助 Union-Find 算法，是不是很簡(jiǎn)單呢？
PS：我認(rèn)真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
三、簡(jiǎn)單總結(jié)
使用 Union-Find 算法，主要是如何把原問題轉(zhuǎn)化成圖的動(dòng)態(tài)連通性問題。對(duì)于算式合法性問題，可以直接利用等價(jià)關(guān)系，對(duì)于棋盤包圍問題，則是利用一個(gè)虛擬節(jié)點(diǎn)，營(yíng)造出動(dòng)態(tài)連通特性。
另外，將二維數(shù)組映射到一維數(shù)組，利用方向數(shù)組 d 來簡(jiǎn)化代碼量，都是在寫算法時(shí)常用的一些小技巧，如果沒見過可以注意一下。
很多更復(fù)雜的 DFS 算法問題，都可以利用 Union-Find 算法更漂亮的解決。LeetCode 上 Union-Find 相關(guān)的問題也就二十多道，有興趣的讀者可以去做一做。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對(duì)應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星！
