一 理论知识
1 定义：
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）
的合并及查询问题。
2 主要操作：
初始化：
把每个点所在集合初始化为其自身。
通常来说，这个步骤在每次
使用该数据结构时只需要一次，无论何种实现方式，
时间复杂度
均为 O(N)。
查找：
查找元素所在的集合，即根节点。
合并：
将两个元素所在的集合合并为一个集合。
3 简单实现：
int par[MAX_N], rank[MAX_N];
//加了一个rank数组记录树的高度
//避免像二叉搜索树退化成单链表
//注意在题目数据过大时，可以不
//记录树的高度，否则会超时。
void Init(int n){
int i;
for(i=0; i<n; i++){
par[i]=i;
rank[i]=0;
}
}
int Find(int x){ //注意体会在递归的过程中进行路径压缩
if(x!=par[x])
par[x]=Find(par[x]);
return par[x];
}
void unite(int x, int y){
x=Find(x);
y=Find(y);
if(x==y) return;
if(rank[x]<rank[y]){
par[x]=y;
}
else{
par[y]=x;
if(rank[x]==rank[y])
rank[x]++;
}
}
二 简单应用
1. 家族关系（最简单的应用）
描述
若某个家族人员过于庞大，要判断两个是否是亲戚，确实
还很不容易，现在给出某个亲戚关系图，求任意给出的两个人
是否具有亲戚关系。 规定：x和y是亲戚，y和z是亲戚，那么x
和z也是亲戚。如果x,y是亲戚，那么x的亲戚 都是y的亲戚，
y的亲戚也都是x的亲戚。
输入格式
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），
分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：
每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Ai和Bi具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj
是否具有亲戚关系。
输出格式
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”
或“不具有”亲戚关系。
输入样例：