摘要
并查集可以快速查找多個點之間是否連接配接，以及快速連接配接多個點。并且并查集使用數組的資料結構實作。那麼如何利用數組的結構實作？以及為什麼能夠快速查找和連接配接呢？文章将給出答案。
假如有n個村莊，有些村莊之間有連接配接的路，有些村莊之間沒有連接配接的路。那麼如何快速地查詢其中的兩個村莊是否有連接配接的路？如何快速地連接配接兩個村莊之間的路呢？
并查集就能辦到這種快速查找和連接配接的問題。它的查詢和連接配接的均攤時間複雜度都是O(a(n))，a(n) < 5，是解決這種問題首先要選擇的資料結構。
使用數組、連結清單、平衡二叉樹或者集合（Set）也是可以實作，但是在查詢和連接配接的時間複雜度上都是 O(n)，遠低于并查集的時間複雜度。
通過字面意思看出，并查集的兩個核心操作就是查找、合并：
- 查找（Find）：查找元素所在的集合（集合不是隻 Set 這樣的資料結構，而是廣義的資料集合）
- 合并（Union）：将兩個元素所在的集合合并成一個集合。
在并查集中實作查找和合并有2種不同的思路：
- Find 優先，達到 Find 的時間複雜度為 O(1)，但 Union 的時間複雜度為 O(n)；
- Union 優先，達到 Union 的時間複雜度為 O(logn), 同時 Find 的時間複雜度也能達到 O(logn)，甚至可以優化到 O(a(n))，a(n) < 5 的情況。
這兩種思路的本質就在于存儲資料的方式不同，造成的不同的時間複雜度，兩種思路沒有高低之分，使用哪一種，要根據實際的應用場景來決定。
存儲資料
假設并查集處理的資料都是整型，那麼就可以用整型數組來存儲資料，如下圖所示的集合：
通過圖中可以看出，0、1、3屬于同一集合，2單獨屬于一個集合，4、5、6、7屬于同一集合。上圖展示的是 Find 優先思路存儲的資料。
由圖中可以看出，并查集是可以用數組實作的樹形結構。
如果看過前幾期的文章，會發現之間實作的二叉堆、優先級隊列也是用數組來實作的。
用代碼實作并查集之前，需要先定義一些接口：
- 查找 v 所屬的集合（根節點）
int find(int v); - 合并 v1、v2 所屬的集合
void union(int v1, int v2); - 檢查 v1、v2 是否屬于同一個集合
boolean isSame(int v1, int v2) 因為已經有查找 v 所屬的集合接口，那麼檢查 v1、v2 是否屬于同一個集合的代碼就很好實作：
public boolean isSame(int v1, int v2) {
return find(v1) == find(v2);
} 最後一項準備工作，就是确定好初始化的規則，這裡規定，當初始化時，數組中的每一個元素都各自屬于自己的集合，如下圖：
實作的代碼如下：
// 數組
protected int[] parents;
protected UnionFind(int capacity) {
if (capacity < 0) {
throw new IllegalArgumentException("capacity mush be >= 1");
}
parents = new int[capacity];
for (int i = 0; i < parents.length; i++) {
parents[i] = i;
}
} 代碼中的 capacity 是确定集合的容量，并按照這個容量初始化一個數組。
Quick Find
以上面初始化的數組為例（數組中有0到4的元素），Quick Find 為了讓 Find 的時間複雜度成為 O(1)。是以在合并的時候，就盡量保證元素到所屬的集合（即根節點）路徑短一些。為了達到這個目标，在将一個集合合并到其中一個集合中時，就直接将其中的一個集合根節點指向另外一個集合的根節點。
比如在已經初始化的數組中，0 所在的集合是 0（即根節點是 0），1 所在的集合是 1...4 所在的集合是4，之後執行如下 union 函數時：
- union(1, 0): 1->0，0->0；
- union(1, 2): 1->2, 0->2;
- union(3, 4): 3->4, 4->4;
- union(0, 3): 0->4, 1->4, 2->4, 3->4, 4->4;
由上面流程可以看出，當一個元素的集合A合并到兩外一個元素的集合B是，會把集合A中的所有元素都指向集合B的根節點（這就是 O(n) 的本質）。
在寫代碼之間，需要統一一下做法，若 0 的根節點是 0，即數組中 0 索引存放的元素是 0。
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
// 将 p1 集合中的元素都指向 p2（根節點）
for (int i = 0; i < parents.length; i++) {
if (parents[i] == p1) {
parents[i] = p2;
}
}
} 代碼中可以看到 find() 函數，這個是查找元素所在集合的函數。因為集合中的元素都直接指向根節點，是以就可以通過索引來擷取根節點（這也是 O(1) 本質）：
public int find(int v) {
rangeCheck(v);
return parents[v];
} 代碼中的 rangeCheck() 函數是檢查元素 v 是否合法：
void rangeCheck(int v) {
if (v < 0 || v >= parents.length) {
throw new IllegalArgumentException("v is out of bounds");
}
} Quick Union
Quick Union 是保證合并和查找盡量均衡，是以當兩個集合合并的時候，是把一個集合的根節點指向另外一個集合的根節點。
還是以0到4的數組為例：
- union(1, 0): 1->0, 0->0;
- union(1, 2): 1->0->2, 2->2;
- union(3, 1): 3->4->2, 1->0->2;
通過流程可以看出，當集合A合并到集合B時，集合A的根節點直接指向集合B的根節點：
public void union(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 == p2) return;
// p1 指向 p2
parents[p1] = p2;
} 下面看一下 find() 函數的代碼實作：
public int find(int v) {
rangeCheck(v);
while (v != parents[v]) {
// 當索引和存放的元素相等時，就是根節點
v = parents[v];
}
return v;
} 檢視合并和查找代碼時，可以看出最消耗時間的是查找。但是整個集合的結構類似樹結構，是以查找的耗時可以縮短到 O(logn)。
總結
- 并查集可以解決多點之間的連接配接和查詢問題；
- 可以優先查找或者優先合并，帶來的時間複雜度都是不同的，兩者沒有優劣之分；
- 并查集可以通過數組來實作。