一、并查集的概念：
首先，為了引出并查集，先介紹幾個概念：
1、等價關系（equivalent relation）
自反性、對稱性、傳遞性。
如果a和b存在等價關系，記為a~b。
2、等價類：
一個元素a(a屬于s)的等價類是s的一個子集，它包含所有與a有關系的元素。注意，等價類形成對s的一個劃分：s的每一個成員恰好互斥地出現在一個等價類中。為了确定是否a~b，我們僅需驗證a和b是否屬于同一個等價類即可。
3、并查集：
即為等價類，同一等價類（并查集）中元素兩兩存在等價關系，不同并查集元素之間沒有等價關系。
4、相關性質：find/union
輸入資料最初是n個集合的類（collection），每個集合含有一個元素。初始的描述是所有的關系均為false（自反的除外）。每個集合都有一個不同的元素，進而s(i)&&s(j) = null，這使得這些集合是不相交的（disjoint）。
此時有兩種運算可以進行，即找出給定元素所屬的集合和合并兩個集合。
一種運算是find，它傳回包含給定元素的集合（即等價類）的名字。
另一種運算是添加關系。如果我們希望添加關系a~b，那麼我們首先需要知道a和b是否已經存在關系。這可以通過對a和b執行find檢驗它們是否屬于同一個等價類來完成。如果它們不在同一類中，那麼我們使用求并運算（union），這種運算把含有a和b的兩個等價類合并成一個新的等價類。
二、并查集的基本資料結構：
我們直接引出表示并查集的最佳資料結構，至于為什麼不選擇諸如連結清單等其他資料結構，可以參考《算法導論》和《資料結構和算法分析》。
在這裡，我們使用樹來表示每一個集合，因為樹上的每一個元素都有相同的根。這樣，我們就可以用根來命名所在的集合。
那麼對于每一個元素，我們應該記錄其所在的集合，這裡，我們可以假設樹被非顯式地存儲在一個數組中：數組的每個成員p[i]表示元素i的父親。如果i是根，那麼p[i]=0（也可以設定為p[i]=i）。
對于這樣一個集合，當我們執行兩個集合的union運算，我們是一個節點的根指針指向另一棵樹的根節點。
union(5,6)：
union(7,8)：
union(5,7)：
經過這樣的過程後，上面的樹的非顯式表示（第一行為節點i的父節點p[i]，第二行為節點i）即為：
5
7
1
2
3
4
6
8
或者（根節點p[i]=i）
三、并查集操作實作：
現在，我們考慮上面所提及的find-union操作的具體實作。
并查集操作：
makeset(int x[])：建立一個新的集合，其唯一成員就是x。
unionset(int x, int y)：将包含x和y的動态集合（比如s(x)和s(y)）合并為一個新的集合（即這兩個集合的并集）。
int findset(int x)：傳回x所在的集合編号。
聲明：
p[]數組——p[i]的值即為節點i的父節點
numsets——const常量，表示初始集合的個數，亦即初始元素的個數
makeset(int x[])函數：
void makeset(int x[])
{
int i;
for(i=0;i<numsets;i++)
{
p[i] = 0;//or p[i] = i
}
}
函數解析：
這個初始化過程，即是将數組中每個元素進行父節點指派，這樣即可确定元素的所屬集合。由于初始化時，每個元素各自為單獨的集合，是以，我們設定每一個元素的父節點為0（或節點自己）。
unionset(int x, int y)函數：
void unionset(int x, int y)
int a = findset(x);
int b = findset(y);
p[b] = a;
unionset函數實作的是将兩個元素對應的集合合并起來。在這裡，我們實作的是基礎方法，其優化方法在後面的優化部分會有講解。
這裡的基礎方法，實作的思想為：将兩個集合合并的方法，即是将一個集合的根節點的父節點設定為另一個集合的根節點。
根據上面的思想，這裡的步驟就顯而易見了：
首先通過findset函數得到兩個元素對應的集合編号，然後将其中一個集合的根節點父節點設定為另一集合的根節點，即完成了所有的合并操作。
findset(int x)函數：
int findset(int x)
if( p[x] <= 0) // or if( p[x] == x )
return x;
else
return findset(p[x]);
根據查找步驟，如果節點的父節點為0（或節點自己），那麼就傳回節點自己，因為該節點即為該樹的根節點；如果節點的父節點不為0（或者不是節點自己），那麼就說明該節點存在父節點，那麼就傳回該父節點所在的集合編号，此集合編号亦為該節點的集合編号。
根據上面的代碼，我們發現其是由遞歸的算法思想來實作的，遞歸終止條件為查找到根節點處，遞歸模式的理論基礎為節點所屬集合與節點的父節點所屬集合是同一集合。
四、并查集操作的優化：
首先，我們先看這樣一個例子：
初始時，我們有5個元素，各自形成5個獨立的集合：
現在，我們按照前面的unionset函數進行這樣一些集合合并操作：
unionset(2,1):
unionset(3,1):
unionset(4,1):
現在，我們考查這個過程，當我們執行完三次unionset操作後，這個集合便成為了一個連結清單形式。這樣導緻的問題就是查找效率會很低。
為什麼連結清單的整體性能較差呢？
對于并查集，我們經常使用的是find-union操作。如果使用連結清單資料結構來存儲并查集，我們常常指定連結清單的第一個元素作為它所在集合的代表。那麼對于查找find操作，對于尾端的元素，要查找至連結清單頭節點，需要周遊整個連結清單，其時間複雜度為o(n)。而對于合并union操作，将兩個元素所在的集合合并起來，即将兩個連結清單合并起來，一般可以使用兩種方法，一種是頭頭相連，一種是頭尾相連。但是，無論是哪種合并方法，都需要經曆查找過程，找到連結清單的頭節點，然後再進行連接配接操作。綜合看來，其查找和合并操作所需的時間複雜度高于根樹的實作方法。
在這裡，我們所采用的優化方式是盡量避免合并之後樹的深度過分增加的啟發式政策。
第一種啟發式是按秩合并（union by rank）。其思想是使包含較少節點的樹的根指向包含較多節點的樹的根。對每個節點，用秩表示節點高度的一個上界。在按秩合并中，具有較小秩的根在union操作中要指向具有較大秩的根。
第二種啟發式即路徑壓縮（path compression）。路徑壓縮在一次findset2操作期間執行而與用來執行unionset的方法無關。設操作為findset2(x)，此時路徑壓縮的效果是，從x到根的路徑上的每個節點都使它的父節點變為根。
現在，一一講解這兩種方法：
1、按秩合并（union by rank）：
這裡，我們需要增加字段rank。在初始化過程中，需要對每個節點（集合）進行rank字段的初始化。
(1)、makeset(int x[])
void makeset(int x[])
p[x[i]] = 0;//or p[i] = i
rank[i] = 0;
(2)、按秩合并過程：具有較小秩的根在union操作中要指向具有較大秩的根。
void unionbyrank(int x, int y)
int fx = findset(x);
int fy = findset(y);
if( rank[fx] > rank[fy])
p[fy] = fx;
p[fx] = fy;
if(rank[fx] == rank[fy])
rank[fy]++;
這裡主要集中這樣幾個問題：
a、為什麼要找到根節點？
b、哪些情況下需要更新秩？
c、對于不同的秩的大小比較情況應采取何種不同的措施？
解答：
a、我們合并兩個元素，即是合并兩個元素分别對應的集合，也就是兩棵不同的樹。為了使合并後的樹的深度的增加盡可能小，我們應該考慮的是樹的秩，即根節點的秩，而不是兒子節點的秩。
b、更新秩的原因在于合并後的集合的秩發生了變化。而發生變化的情況隻有一種：那就是合并前的兩個集合的秩相等，這樣必然會有其中一個集合的樹的根指向另外一個集合的樹的根節點，這樣新的集合的秩必然增加1。
c、我們在合并時采用秩小的樹合并到秩大的樹，比較之後，通過改變p[i]即可實作合并過程。
舉例說明這樣合并的好處：
現有操作union(5,3)：
對于傳統的union操作，即函數unionset(5,3)：
首先，找到5,3對應的集合，即findset(5)=4, findset(3)=1；
然後，p[1] = 4；
于是得到如下集合1：
對于按秩合并，即函數unionbyrank(5,3):
然後，由于4的rank小于1的rank，進而有p[4] = 1；
于是得到如下集合2：
通過對比集合1和集合2，顯然集合2的構造更為均勻，會給查找操作帶來很大的便利。
2、路徑壓縮（path
compression）：
對于路徑壓縮，其關鍵過程在于一定要使樹的結構偏向于直連根節點的節點數增加，進而減少find操作。
對于整個路徑壓縮過程，其核心就在于每次findset操作過後均需将周遊到的節點動态直連到根節點上。也就是說，每次findset時都會對整個集合的樹結構進行調整。
void findsetwithpathcompression(int x)
if(p[x] == 0) //or if(p[x] == x)
return p[x] = findsetwithpathcompression(p[x]);
仔細觀察findsetwithpathcompression()函數與findset()函數的差別，其差別就在于 p[x]
= findsetwithpathcompression(p[x])。這個差別所産生的影響在什麼地方呢？
舉個例子：
對于下圖所示的集合（根樹），我們希望找到6所對應的集合編号：
顯然，對于findset(6)，其需要周遊節點6,2,1,4，經過四個步驟才能找到根節點，得到集合編号4。
而對于findsetwithpathcompression(6)，其同樣會周遊節點6,2,1,4，但是，由于p[x] = findsetwithpathcompression(p[x])的作用，p[6] = p[2] = p[1] =4。
進而，整個集合的根樹就發生了結構性調整：
樹的結構發生的變化帶來的是後面查找操作的簡化，同時沒有改變整個集合的内容（我們不關注集合是怎樣實作和存放的，我們關注的是集合中到底有哪些關系和元素）。
五、并查集應用執行個體：
描述
若某個家族人員過于龐大，要判斷兩個是否是親戚，确實還很不容易。現給出某個親戚關系圖，求任意給出的兩個人是否具有親戚關系。 規定：x和y是親戚，y和z是親戚，那麼x和z也是親戚。如果x,y是親戚，那麼x的親戚都是y的親戚，y的親戚也都是x的親戚。
input
第 一行：三個整數n、m、p (n< =5000,m< =5000, p< =5000)，分别表示有n個人，m個親戚關系，詢問p對親戚關系。
接下來的m行：每行兩個數mi、mj (1< =mi、mj< =n)，表示mi和mj具有親戚關系。
接下來的p行：每行兩個數pi、pj，詢問pi和pj是否具有親戚關系。
output
p行，每行一個’yes’或’no’。表示第i個詢問的答案為“具有”或“不具有”親戚關系。
問題分析
對于該問題，初步的感覺是利用圖的連通性來實作，但是，由于資料量的巨大，要使用圖來實作這樣一個過程是不現實的。
注意，題目中的規定實質上指定了x與y的等價關系。是以，綜合此題，我們可以使用并查集的方式來實作題目求解。這樣，題意就轉換為：
n個元素，通過m個等價關系建構集合，判斷p對元素是否在同一集合中。
代碼解答
#include <stdio.h>
#define max 5000
int p[max];
void makeset(int x);
void unionset(int x, int y);
void findsetwithpathcompression(int x);
int main(void)
int n,m,p;
int a,b;
int x,y;
scanf("%d %d %d", &n, &m, &p);
makeset(n);
while(m--)
scanf("%d %d", &a, &b);
unionset(a,b);
while(p--)
scanf("%d %d",&x,&y);
if( findsetwithpathcompression(x) == findsetwithpathcompression(y) )
printf("yes\n");
else
printf("no\n");
}
void makeset(int x)
for(i = 0; i < x; i++ )
p[i] = 0;
other functions is writen in above content.