高级数据结构－并查集及实现
并查集是一种简单的用途广泛的集合， 并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。并查集是一种可以方便地进行以下三种操作的数据结构：
合并两个集合;
将一元素并入另一集体;
判断两个元素是否属于同一个集合。
例如，可以用数组很方便地实现一个并查集，对一个含有n个元素的并查集，可以用一个长度为n的数组实现，主要设计以下四种操作：
初始化并查集：每个元素赋一不同的值，时间复杂度为O(n)。
合并两个集合A和B：将所有标记为B集合的元素的标记变为A集合的标记，时间复杂度为O(n)。
将一元素a并入集合A:时间复杂度为O(1)。
判断两元素是否属于同一集合：只须比较标记，时间复杂度为O(1)。
并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。它支持三种操作:
MakeSet(x): 创建一个只包含一个元素x的并查集。
Find(x, S): 判断x是否在集合S中。
Union(A, B):合并两个并查集A和B 并查集与树可以将每一棵树都看成是元素的集合,从而可以用树来表示并查集。
对于并查集来说，每个集合用一棵树表示。集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。
设 S1= {0, 6, 7, 8 }，S2= { 1, 4, 9 }，S3= { 2, 3, 5 }
为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到 n-1。其中 n 是最大元素个数。在双亲表示中，第 i 个数组元素代表包含集合元素 i 的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息( ≥ 0 )，集合元素个数信息用负数表示。
0 1 2 3 4 5 6 7 8 9
-1 4 -1 2 -1 2 0 0 0 4
Union操作的加权规则
为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果以 i 为根的树中的结点个数少于以 j 为根的树中的结点个数，即parent > parent[j]，则让 j 成为 i 的双亲，否则，让i成为j的双亲。此即Union的加权规则。
parent[0](== -4) < parent[4] (== -3)
WeightedUnion(int Root1, int Root2) {
//按Union的加权规则改进的算法
int temp = parent[Root1] + parent[Root2];
if ( parent[Root2] < parent[Root1] ) {
parent[Root1] = Root2; //Root2中结点数多
parent[Root2] = temp; //Root1指向Root2
}
else {
parent[Root2] = Root1; //Root1中结点数多
parent[Root1] = temp; //Root2指向Root1
}
}
题目： 亲戚(Relations)
或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及.在这种情况下，最好的帮手就是计算机。
为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和B en是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关心的亲戚关系的提问，以最快的速度给出答案。
参考输入输出格式 输入由两部分组成。
第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有两个数ai, bi，表示已知ai和bi是亲戚.
第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000)，每行为ci, di，表示询问ci和di是否为亲戚。
对于每个询问ci, di，若ci和di为亲戚，则输出Yes，否则输出No。
样例输入与输出
输入relation.in
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
输出relation.out
Yes
No
Yes
很简单的
