一 ，并查集的構造
① 設定一個集合杨赤，叫并查集敞斋，即 Disjoint Set，功能是檢查 圖中 是否出現了 環(huán)
② 往集合里面添加邊疾牲，怎么添加呢植捎。取邊的起點和終點，判斷兩點是否都在集合里面阳柔，如果都在焰枢，則出現了環(huán)，如果不在舌剂，將兩個點 放入集合中济锄。
③ 繼續(xù)添加下一條邊，如果沒有邊了霍转，還沒有找到環(huán)荐绝，就是沒有環(huán)了
二，數組以樹的形式實現
上面所講的就是基本的思想了避消，下面講如何具體實現
① 由于集合操作并不方便低滩，所以便設法使用數組實現
② 由于上面所說的添加邊 可以看成是一組點的集合 連接 另外一組點的集合，所以我們只要隨便讓集合的某一點 連接 另外一個集合的任意一點 就行了
這樣就可以讓所有點處于連通狀態(tài)
③ 基于上述所講岩喷，我們可以將點以樹的形式連接恕沫，為什么是樹呢？因為集合中沒有環(huán)纱意，所以最后畫出來的圖形就是樹了昏兆。
④ 由于連接的隨意性， 這種連接方式妇穴，并不能正確表示一張圖爬虱，只是能表示所有點是連接在一起的，且這種圖畫出來是樹的形式腾它。
⑤ 所以跑筝，我們可以構造一個 parent 數組，什么意思呢 瞒滴？ 就是 parent[x]=y, 指 x 的父節(jié)點是 y ,
為什么要 定義一個父節(jié)點呢曲梗？ 定義父節(jié)點的意思是 你可以通過父節(jié)點找到這個集合的根 赞警，根就是 所有點 都由 這個點 出發(fā)得到的。
那么虏两，為什么要找到這個根呢愧旦？ 即這樣做的優(yōu)點。
優(yōu)點1定罢，在添加邊的時候笤虫，可以通過查找 邊上兩個點的根結點是否存在，是否相同祖凫，達到判斷兩個點是否在之前的集合中出現過的效果
優(yōu)點2琼蚯，可以在 加邊 時減少樹的深度，之后查找 根節(jié)點時就可以減少步驟
三惠况，壓縮路徑
且看我上面優(yōu)點 2 這一句 “但如果讓 3 的父節(jié)點為 0 深度增加了一層” 遭庶，其實如果但如果讓 0 的父節(jié)點為 3 深度就沒有增加了
之前的代碼中，我們這一步那個時那個的父節(jié)點我們并沒有對此做一個判斷稠屠，來判斷哪一個成為 父節(jié)點 樹的深度會更少峦睡。
這樣子就有一個問題，如果一直是
0-1 1-2 2-3 3-4 這樣子就會讓樹的深度一直增加权埠，這樣就會讓 find_root 函數時間復雜度在最壞的情況下達到 o(n) ,即每個點都要查找榨了。
所以，我們使用 rank 數組來記錄 樹的深度弊知，如 rank[x]=y 表示 以 x 點為根結點的話，樹的深度為 y
題目：
https://www.luogu.com.cn/problem/P1551
#include<iostream>
using namespace std;
int a[5001],rank[5001];
int n,m,p;
//n個人粱快，m個親戚關系秩彤，詢問p對親戚關系
//尋找該點的最最最原始的結點，直到找到沒有父節(jié)點的0為止
int find_root(int x,int a[]){
//先將根節(jié)點設為自己
int x_root = x;
//往上找事哭，如果不是0就繼續(xù)
while(a[x_root]){
x_root = a[x_root];
}
//返回根節(jié)點
return x_root;
}
//合并
int union_vertices(int x,int y,int a[],int rank[]){
//找到x和y的根節(jié)點
int x_root = find_root(x,a);
int y_root = find_root(y,a);
//如果相同就不用并了漫雷，是一家人
if(x_root == y_root){
return 0;
}else{
//a[x_root]=y_root;
//如果x的層數比y的層數高，就把y并到x上鳍咱，總層數不變
if(rank[x_root] > rank[y_root]){
a[y_root] = x_root;
}else if(rank[y_root] > rank[x_root]){
a[x_root] = y_root;
}else{//如果層數相同降盹，就隨便并一下，層數加一
a[x_root] = y_root;
rank[y_root]++;
}
return 1;
}
}
int main(){
cin>>n>>m>>p;
while(m--){
int x,y;
cin>>x>>y;
union_vertices(x,y,a,rank);
}
while(p--){
int x,y;
cin>>x>>y;
int x_root = find_root(x,a);
int y_root = find_root(y,a);
if(x_root == y_root){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}
鏈接：
https://www.cnblogs.com/asdfknjhu/p/12515480.html
https://www.bilibili.com/video/BV13t411v7Fs
