并查集
并查集（Union-Find Set）省店，也稱為不相交集數據結構（Disjointed Set Data Structure）。是指一系不相交的集合（Sets），提供合并（Union）和查找(Find)兩種操作。
- find（I）
find(i)即查找I所歸屬的集合山涡，通常我們使用find(i)和find(j)判斷i和j是否連通，即是否屬于同一個集合 - union(int i , int j)
顧名思義，union方法即將I和J所在的兩個集合連通起來鸭丛，執(zhí)行這個方法后霍殴，I所在集合和所有元素和J所在集合的所有元素都連通
適用場景
Union-Find算法最常見的使用場景就是動態(tài)連通（dynamic-connectivity）了
我們在浩如煙海的數據中要判斷兩個元素是否連通，是很有實際意義的系吩。比如計算機網絡中兩臺不同計算機是否連通，社交網絡中兩個人是否有聯系妒蔚，一張圖片中兩個像素之間的聯系等穿挨。
Quick Find
我們首先來看一下第一種實現方案。數據結構我們用數據來實現肴盏，假設一個集合有N個元素科盛，我們用一個長度為N的數組來存儲。array[0]...array[N-1]菜皂。相同集合內的元素贞绵，array中的元素相等。
public class QuickFindUF
{
private int[] id;
public QuickFindUF(int N){
id = new int[N];
for(int j = 0 ; j < N ; j ++){ //N array accesses
id[j] = j;
}
}
public boolean connected(int p , int q){
return id[p] == id[q]; //2 array accesses
}
public void union(int p , int q){ //at most 2N + 2 array accesses
int pid = id[p];
int qid = id[q];
for(int i = 0 ; i < id.length ; i ++){
if(id[i] == pid) id[i] = qid;
}
}
}
我們看到恍飘，quick-find算法find是很快的榨崩，時間復雜度只有1, 但是union操作相當耗時，quick-find算法的時間度是N的平方章母。這就意味著母蛛，當處理大量數據時，耗時指數上升乳怎。換個說法彩郊，假設計算機能力提高十位，而我們的數據量擴大十倍蚪缀，我們的速度反而降低了十倍秫逝。
Quick-Union
我們再來看一下另一種實現-Quick-Union算法。數據結構我們保持不變询枚，依然是一個數組违帆，但數據中的元素不再是"groupId"。我們邏輯上把這個數據想象成一棵樹哩盲，而數據中的元素存放的是父節(jié)點前方。
這種情況下，假設我們要計算union(p , q)廉油，只需要將p所在樹的根節(jié)點設置成q所在樹的根節(jié)點即可惠险，話不多說，上圖抒线。
quick-union顧名思義班巩，是快速union的算法，與quick-find相比，不需要遍歷數組抱慌，將所有集合中元素都修改為新的"groupId"逊桦。而只需要將兩個集合的根節(jié)點連接到一起即可。我們看下代碼：
public class QuickUnionUf{
private int[] id;
public QuickUnionUf(int N){
id = new int[N];
for(int j = 0 ; j < N ; j ++){ //N array accesses
id[j] = j;
}
}
private int root(int p){ //depth of p array accesses
while(id[p] != p){
p = id[p];
}
return p;
}
public boolean connected(int p , int q){
return root(id[p]) == root(id[q]); //depth of p and q array accesses
}
public void union(int p , int q){ //depth of p and q array accesses
int i = root(p);
int j = root(q);
id[I] = j;
}
}
weighted-quickUnion
以上兩種算法復度度都不夠好抑进，我們再看下如何改進强经。quick-union我們已經分析過了，相比于quick-find寺渗，通過樹的根節(jié)點的改變匿情，減少了union的時間復雜度。但是在極端情況下信殊，樹可能會出現不平衡的狀況炬称，最壞情況時間復雜度為N。我們的思路是要盡量使樹平衡涡拘，因為平衡樹深搜的復雜度是lgN玲躯，所以我們優(yōu)化了quick-union。
public class weightedQuickUnionUF{
private int[] id;
private int[] sz;
private int count;
public WeightedQuickUnionUF(int N){
count = N;
id = new int[N];
for(int i=0; i<N; i++) id[i] = I;
sz = new int[N];
for(int i=0; i<N; i++) id[i] = 1;
}
public int count(){
return count;
}
public boolean connected(int p, int q){
return find(p) == find(q);
}
private int root(int p){
while( p != id[p]) p = id[p];
return p;
}
public void union(int p, int q){
int i = root(p);
int j = root(q);
if( i == j) return;
//判斷兩棵樹大小鳄乏，將小樹掛在大樹上
if( sz[i] < sz[j]) { id[i] = j; sz[j] += sz[I];}
else { id[j] = i; sz[i] += sz[j]; }
count--;
}
}
path-compression
這樣就結束了嗎跷车？還有沒有什么優(yōu)化的點？隨著數據的增加橱野，樹的深度不斷增加姓赤，性能會逐漸變差。這個時候仲吏，如果我們在計算一個node的root時不铆，將node為根的樹摘下來，掛在當前樹的根結點上裹唆，會降低樹的深度誓斥，也就是提高效率，降低時間復雜度许帐。這種方法叫路徑壓縮：path-compression劳坑。
要做這個修改其實很簡單，我們只需要修改一下root方法成畦，就可以了距芬。
private int root(int p){
while( p != id[p]) {
id[p] = id[id[p]]; //加了這一句，當循環(huán)結束后循帐，就會把p為根結點的樹摘下來框仔，掛在所在樹的根結點上
p = id[p];
}
return p;
}
