并查集的應用十分廣泛，包括一些算法，當應用上并查集的時候，也會更容易實作。下面總結下并查集的相關内容。
什麼是并查集？
個人的了解是：并查集就是對集合三種常用操作的再一次抽象。分别是集合的合并（Union）、元素的搜尋（Find）和對集合的分解。因為這3中操作非常常用并且又不囿于集合，是以就把這一組操作抽象成一個獨立的資料結構。
标準定義
在一些應用問題中，需要将n個不同的元素劃分成一組不相交的集合。開始時每個元素自成一個單元素集合，然後按照一定規律将歸于同一組元素的集合合并，在此過程中需要反複查詢某個元素歸屬于哪個集合的運算，适合于描述這類問題的抽象資料類型稱為并查集（union-find set）。
并查集的3種操作！
從上面的定義也可以看出來，并查集的三種操作是：
（1）Union(Root1, Root2):把子集合Root2并入集合Root1中。要求這兩個集合互不相交，否則不執行合并。
（2）Find(x)：搜尋單元素x所在的集合，并傳回該集合的名字。
（3）UnionFindSets(s):構造函數，将并查集中s個元素初始化為s個隻有一個單元素的子集合。
并查集的一種實作方案
實作并查集的方式有多種，這裡主要總結用**樹結構（父指針表示法）**來實作并查集及其相關操作。
用這種實作方式，每個集合用一棵樹表示，樹的每一個節點代表集合的一個單元素。所有各個集合的全集合構成一個森林，并用樹與森林的父指針表示法來實作。其下标代表元素名。第I個數組元素代表包含集合元素I的樹節點。樹的根節點的下标代表集合名，根節點的父為-1，表示集合中元素個數。
下面看一個例子：
全集合是S = {0，1，2，3，4，5，6，7，8，9}，初始化每個元素自成為一個單元素子集合。（書上原圖，感覺挺清晰的）
經過一段時間的計算，這些子集合并成3個集合，他們是全集合S的子集合：S1 = {0，6，7，8}，S2= {1，4，9}，S3 = {2，3，5}。則表示他們并查集的樹形結構如下圖：
上面數組中的元素值有兩種含義：
（1）負數表示目前節點是樹的根節點，負數的絕對值表示樹中節點的個數，也即集合中元素的個數。
（2）正數表示其所屬的樹的根節點，由樹形表示很容易了解，這也是樹的父指針表示的定義。
經過上面對相關資料的組織，再回頭來看并查集的3中核心操作是怎樣依托于樹來實作的：
（1）将root2并入到root1中，其實就可以直接把root2的數組元素（就是他的父節點）改成root1的名字（就是他所在的數組下标）。
下面的圖表示了合并兩個子集合的過程：
并查集的了解與實作總結 （2）查找x所屬于的根節點（或者說是x所屬于的集合），就可以一直找array[x]，直到array[x]小于0，則證明找到了根（所在集合）。
下面的圖示意了查找一個節點所屬集合的過程：
（3）将整個集合初始化為單元素集合，其實就是建立樹的父指針數組的過程，把數組元素全初始化為-1，也就表示了每個元素都各占一個集合。并查集的了解與實作總結
有了上面的理論，代碼也比較容易實作出來！下面給出了一個代碼的執行個體：
/*
*樹結構建構并查集，其中樹用父指針形式表示
*/
#include <iostream>
const int DefaultSize = 10;
class UFSets { //集合中的各個子集合互不相交
public:
UFSets(int sz = DefaultSize); //構造函數 (并查集的基本操作)
~UFSets() { delete[] parent; } //析構函數
UFSets& operator = (UFSets& R); //重載函數：集合指派
void Union(int Root1, int Root2); //兩個子集合合并 (并查集的基本操作)
int Find(int x); //搜尋x所在集合 (并查集的基本操作)
void WeightedUnion(int Root1, int Root2); //權重的合并算法
private:
int *parent; //集合元素數組(父指針數組)
int size; //集合元素的數目
};
UFSets::UFSets(int sz) {
//構造函數，sz是集合元素的個數,父指針數組的範圍0到sz-1
size = sz; //集合元素的個數
parent = new int[size]; //開辟父指針數組
for (int i = 0; i < size; i ++) { //初始化父指針數組
parent[i] = -1; //每個自成單元素集合
}
}
int UFSets::Find(int x) {
//函數搜尋并傳回包含元素x的樹的根
while (parent[x] >= 0) {
x = parent[x];
}
return x;
}
void UFSets::Union(int Root1, int Root2) {
//函數求兩個不相交集合的并，要求Root1與Root2是不同的，且表示了子集合的名字
parent[Root1] += parent[Root2]; //更新Root1的元素個數
parent[Root2] = Root1; //令Root1作為Root2的父節點
}
void UFSets::WeightedUnion(int Root1, int Root2) {
//使用節點個數探查方法求兩個UFSets集合的并
int r1 = Find(Root1); //找到root1集合的根
int r2 = Find(Root2); //找到root2集合的根
if (r1 != r2) { //兩個集合不屬于同一樹
int temp = parent[r1] + parent[r2]; //計算總節點數
if (parent[r2] < parent[r1]) { //注意比較的是負數，越小元素越多,此處是r2元素多
parent[r1] = r2; //r1作為r2的孩子
parent[r2] = temp; //更新r2的節點個數
}
else {
parent[r2] = r1; //...
parent[r1] = temp; //...
}
}
}
代碼的注釋比較詳盡，我就不在贅言。但是有一個注意點我已經寫在了下面！
目前并查集的改進！
的确，有一個極端的狀況使得上面的樹實作的并查集性能低下！問題原因在于，這裡沒有規定子集合并的順序，更确切的說是子集一直在向同一個方向依附：
下面的圖檔展示了當Union(0，1),Union(1，2),Union(2，3),Union(3，4)執行完後的樹的形狀。
在這種極端情況下他編變成了一個單連結清單（退化的樹），這樣的話，用Find函數查找完所有的節點所歸屬的集合将會開銷的時間複雜度為：O(n^2)。
怎樣來改變這種狀況，就是在合并兩個子集的時候，規定順序，代碼中是讓元素多的始終作為父節點，這樣就避免了這種麻煩。
另外還可以用性能更加的查找算法，例如折疊規則壓縮路徑。并查集的一個重要的應用是在圖論中生成最小生成樹的Kruskal算法，充分展現了并查集的優越性和思想，之後會寫相關的博文總結此算法！
參考書目：《資料結構 C++語言描述 第二版》 殷人昆著