-----------
今天講講 Union-Find 算法，也就是常說的并查集算法，主要是解決圖論中「動態(tài)連通性」問題的。名詞很高端，其實特別好理解，等會解釋，另外這個算法的應用都非常有趣。
說起這個 Union-Find，應該算是我的「啟蒙算法」了，因為《算法4》的開頭就介紹了這款算法，可是把我秀翻了，感覺好精妙??！后來刷了 LeetCode，并查集相關的算法題目都非常有意思，而且《算法4》給的解法竟然還可以進一步優(yōu)化，只要加一個微小的修改就可以把時間復雜度降到 O(1)。
廢話不多說，直接上干貨，先解釋一下什么叫動態(tài)連通性吧。
一、問題介紹
簡單說，動態(tài)連通性其實可以抽象成給一幅圖連線。比如下面這幅圖，總共有 10 個節(jié)點，他們互不相連，分別用 0~9 標記：
現(xiàn)在我們的 Union-Find 算法主要需要實現(xiàn)這兩個 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、自反性：節(jié)點p和p是連通的。
2、對稱性：如果節(jié)點p和q連通，那么q和p也連通。
3、傳遞性：如果節(jié)點p和q連通，q和r連通，那么p和r也連通。
比如說之前那幅圖，0～9 任意兩個不同的點都不連通，調用connected都會返回 false，連通分量為 10 個。
如果現(xiàn)在調用union(0, 1)，那么 0 和 1 被連通，連通分量降為 9 個。
再調用union(1, 2)，這時 0,1,2 都被連通，調用connected(0, 2)也會返回 true，連通分量變?yōu)?8 個。
判斷這種「等價關系」非常實用，比如說編譯器判斷同一個變量的不同引用，比如社交網(wǎng)絡中的朋友圈計算等等。
這樣，你應該大概明白什么是動態(tài)連通性了，Union-Find 算法的關鍵就在于union和connected函數(shù)的效率。那么用什么模型來表示這幅圖的連通狀態(tài)呢？用什么數(shù)據(jù)結構來實現(xiàn)代碼呢？
二、基本思路
注意我剛才把「模型」和具體的「數(shù)據(jù)結構」分開說，這么做是有原因的。因為我們使用森林（若干棵樹）來表示圖的動態(tài)連通性，用數(shù)組來具體實現(xiàn)這個森林。
怎么用森林來表示連通性呢？我們設定樹的每個節(jié)點有一個指針指向其父節(jié)點，如果是根節(jié)點的話，這個指針指向自己。比如說剛才那幅 10 個節(jié)點的圖，一開始的時候沒有相互連通，就是這樣：
class UF {
// 記錄連通分量
private int count;
// 節(jié)點 x 的節(jié)點是 parent[x]
private int[] parent;
/* 構造函數(shù)，n 為圖的節(jié)點總數(shù) */
public UF(int n) {
// 一開始互不連通
this.count = n;
// 父節(jié)點指針初始指向自己
parent = new int[n];
for (int i = 0; i < n; i++)
parent[i] = i;
}
/* 其他函數(shù) */
}
如果某兩個節(jié)點被連通，則讓其中的（任意）一個節(jié)點的根節(jié)點接到另一個節(jié)點的根節(jié)點上：
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--; // 兩個分量合二為一
}
/* 返回某個節(jié)點 x 的根節(jié)點 */
private int find(int x) {
// 根節(jié)點的 parent[x] == x
while (parent[x] != x)
x = parent[x];
return x;
}
/* 返回當前的連通分量個數(shù) */
public int count() {
return count;
}
這樣，如果節(jié)點p和q連通的話，它們一定擁有相同的根節(jié)點：
public boolean connected(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
return rootP == rootQ;
}
至此，Union-Find 算法就基本完成了。是不是很神奇？竟然可以這樣使用數(shù)組來模擬出一個森林，如此巧妙的解決這個比較復雜的問題！
那么這個算法的復雜度是多少呢？我們發(fā)現(xiàn)，主要 APIconnected和union中的復雜度都是find函數(shù)造成的，所以說它們的復雜度和find一樣。
find主要功能就是從某個節(jié)點向上遍歷到樹根，其時間復雜度就是樹的高度。我們可能習慣性地認為樹的高度就是logN，但這并不一定。logN的高度只存在于平衡二叉樹，對于一般的樹可能出現(xiàn)極端不平衡的情況，使得「樹」幾乎退化成「鏈表」，樹的高度最壞情況下可能變成N。
所以說上面這種解法，find,union,connected的時間復雜度都是 O(N)。這個復雜度很不理想的，你想圖論解決的都是諸如社交網(wǎng)絡這樣數(shù)據(jù)規(guī)模巨大的問題，對于union和connected的調用非常頻繁，每次調用需要線性時間完全不可忍受。
問題的關鍵在于，如何想辦法避免樹的不平衡呢？只需要略施小計即可。
PS：我認真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
三、平衡性優(yōu)化
我們要知道哪種情況下可能出現(xiàn)不平衡現(xiàn)象，關鍵在于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所在的樹的根節(jié)點下面，那么這里就可能出現(xiàn)「頭重腳輕」的不平衡狀況，比如下面這種局面：
長此以往，樹可能生長得很不平衡。我們其實是希望，小一些的樹接到大一些的樹下面，這樣就能避免頭重腳輕，更平衡一些。解決方法是額外使用一個size數(shù)組，記錄每棵樹包含的節(jié)點數(shù)，我們不妨稱為「重量」：
class UF {
private int count;
private int[] parent;
// 新增一個數(shù)組記錄樹的“重量”
private int[] size;
public UF(int n) {
this.count = n;
parent = new int[n];
// 最初每棵樹只有一個節(jié)點
// 重量應該初始化 1
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
/* 其他函數(shù) */
}
比如說size[3] = 5表示，以節(jié)點3為根的那棵樹，總共有5個節(jié)點。這樣我們可以修改一下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這個數(shù)量級，極大提升執(zhí)行效率。
此時，find,union,connected的時間復雜度都下降為 O(logN)，即便數(shù)據(jù)規(guī)模上億，所需時間也非常少。
PS：我認真寫了 100 多篇原創(chuàng)，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄，持續(xù)更新。建議收藏，按照我的文章順序刷題，掌握各種算法套路后投再入題海就如魚得水了。
四、路徑壓縮
這步優(yōu)化特別簡單，所以非常巧妙。我們能不能進一步壓縮每棵樹的高度，使樹高始終保持為常數(shù)？
這樣find就能以 O(1) 的時間找到某一節(jié)點的根節(jié)點，相應的，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函數(shù)每次向樹根遍歷的同時，順手將樹高縮短了，最終所有樹高都不會超過 3（union的時候樹高可能達到 3）。
PS：讀者可能會問，這個 GIF 圖的find過程完成之后，樹高恰好等于 3 了，但是如果更高的樹，壓縮后高度依然會大于 3 呀？不能這么想。這個 GIF 的情景是我編出來方便大家理解路徑壓縮的，但是實際中，每次find都會進行路徑壓縮，所以樹本來就不可能增長到這么高，你的這種擔心應該是多余的。
五、最后總結
我們先來看一下完整代碼：
class UF {
// 連通分量個數(shù)
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 算法的復雜度可以這樣分析：構造函數(shù)初始化數(shù)據(jù)結構需要 O(N) 的時間和空間復雜度；連通兩個節(jié)點union、判斷兩個節(jié)點的連通性connected、計算連通分量count所需的時間復雜度均為 O(1)。
現(xiàn)在解決這道朋友圈問題就很簡單了：
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();
}
接下文：Union-Find 算法應用
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目，建議收藏！對應的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標星！
