并查集學(xué)習(xí)筆記
并查集（union-find set）是一抽象數(shù)據(jù)類型骚烧。它所處理的是“集合”之間的關(guān)系浸赫，即動(dòng)態(tài)地維護(hù)和處理集合元素之間復(fù)雜的關(guān)系，
當(dāng)給出兩個(gè)元素的一個(gè)無序?qū)?a,b)時(shí)赃绊，需要快速“合并”a和b分別所在的集合既峡，這其間需要反復(fù)“查找”某元素所在的集合”滩椋“并”运敢、“查”和“集”三字由此而來。
合并元素所在集合忠售、查找元素所在集合
數(shù)組實(shí)現(xiàn)
并查集支持的操作
MAKE(x)：建立一個(gè)新的集合传惠，其僅有的成員（同時(shí)就是代表）是x。由于各集合是分離的档痪，要求x沒有在其它集合中出現(xiàn)過涉枫。
UNIONN(x,y)：將包含x和y的動(dòng)態(tài)集合（例如Sx和Sy）合并為一個(gè)新的集合，假定在此操作前這兩個(gè)集合是分離的腐螟。結(jié)果的集合代表是Sx∪Sy的某個(gè)成員愿汰。一般來說，在不同的實(shí)現(xiàn)中通常都以Sx或者Sy的代表作為新集合的代表乐纸。此后衬廷，由新的集合S代替了原來的Sx和Sy。
FIND(x)：返回一個(gè)指向包含x的集合的代表汽绢。
查找
int find(int x) { //用非遞歸的實(shí)現(xiàn)
while (father[x] != x) x = father[x];
return x;
}
int find(int x){//用遞歸的實(shí)現(xiàn)
if (father[x] != x){
return find(father[x]);
} else{
return x;
}
}
合并
void unionn(int r1,int r2){
father[r2] = r1;
}
int main(){
cin >> n >> m;
for (i = 1; i <= n; i++)
father[i] = i; //建立新的集合吗跋，其僅有的成員是i
for (i = 1; i <= m; i++) {
scanf("%d%d",&x,&y);
int r1 = find(x);
int r2 = find(y);
if (r1 != r2){
unionn(r1,r2);
}
}
cin >> q;
for (i = 1; i <= q; i++) {
scanf("%d%d",&x,&y);
if (find(x) == find(y)){
printf("Yes\n");
} else {
printf("No\n");
}
}
return 0;
}
