并查集是什么東西？
它是用來管理元素分組情況的一種數據結構。
他可以高效進行兩個操作：
- 查詢a，b是否在同一組
- 合并a和b所在的組
萌新可能不知所云，這個結構到底有什么用？
經分析，并查集效率之高超乎想象，對n個元素的并查集進行一次操作的復雜度低于O(logn)
?
我們先說并查集是如何實現的：
也是使用樹形結構，但不是二叉樹。
每個元素就是一個結點，每組都是一個樹。
無需關注它的形狀，或哪個節點具體在哪個位置。
?
初始化：
我們現在有n個結點，也就是n個元素。
?
合并：
然后我們就可以合并了，合并方法就是把一個根放到另一顆樹的下面，也就是整棵樹作為人家的一個子樹。
?
查詢：
查詢兩個結點是否是同一組，需要知道這兩個結點是不是在一棵樹上，讓他們分別沿著樹向根找，如果兩個元素最后走到一個根，他們就在一組。
?
當然，樹形結構都存在退化的缺點，對于每種結構，我們都有自己的優化方法，下面我們說明如何避免退化。
- 記錄每一棵樹的高度，合并操作時，高度小的變為高度大的子樹即可。
- 路徑壓縮：對于一個節點，只要走到了根節點，就不必再在很深的地方，直接改為連著根即可。進一步優化：其實每一個經過的節點都可以直接連根。
這樣查詢的時候就能很快地知道根是誰了。
?
下面上代碼實現：
和很多樹結構一樣，我們沒必要真的模擬出來，數組中即可。
int p[MAX_N];//父親
int rank[MAX_N];//高度
//初始化
void gg(int n)
{for(int i=0;i<n;i++){p[i]=i;//父是自己代表是根rank[i]=0;}
}
//查詢根
int find(int x)
{if(p[x]==x)return x;return p[x]=find(p[x])//不斷把經過的結點連在根
}
//判斷是否屬于同一組
bool judge(int x,int y)
{return find(x)==find(y);//查詢結果一樣就在一組
}
//合并
void unite(int x,int y)
{if(x==y)return;if(rank[x]<rank[y])p[x]=y;//深度小，放在大的下面else{p[y]=x;if(rank[x]=rank[y])rank[x]++;//一樣，y放x后，x深度加一}
}實現很簡單，應用有難度，以后有時間更新題。
?
