并查集学习笔记
并查集（union-find set）是一抽象数据类型。它所处理的是“集合”之间的关系，即动态地维护和处理集合元素之间复杂的关系，
当给出两个元素的一个无序对(a,b)时，需要快速“合并”a和b分别所在的集合，这其间需要反复“查找”某元素所在的集合。“并”、“查”和“集”三字由此而来。
合并元素所在集合、查找元素所在集合
数组实现
并查集支持的操作
MAKE(x)：建立一个新的集合，其仅有的成员（同时就是代表）是x。由于各集合是分离的，要求x没有在其它集合中出现过。
UNIONN(x,y)：将包含x和y的动态集合（例如Sx和Sy）合并为一个新的集合，假定在此操作前这两个集合是分离的。结果的集合代表是Sx∪Sy的某个成员。一般来说，在不同的实现中通常都以Sx或者Sy的代表作为新集合的代表。此后，由新的集合S代替了原来的Sx和Sy。
FIND(x)：返回一个指向包含x的集合的代表。
查找
int find(int x) { //用非递归的实现
while (father[x] != x) x = father[x];
return x;
}
int find(int x){//用递归的实现
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;
}
