一、题目
1、原题链接
1249. 亲戚
2、题目描述
或许你并不知道，你的某个朋友是你的亲戚。
他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。
如果能得到完整的家谱，判断两个人是否是亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及。
在这种情况下，最好的帮手就是计算机。
为了将问题简化，你将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。
从这些信息中，你可以推出Marry和Ben是亲戚。
请写一个程序，对于我们的关于亲戚关系的提问，以最快的速度给出答案。
输入格式
输入由两部分组成。
第一部分以 N,M 开始。N 为问题涉及的人的个数。这些人的编号为 1,2,3,…,N。下面有 M 行，每行有两个数 ai,bi，表示已知
ai 和 bi 是亲戚。
第二部分以 Q 开始。以下 Q 行有 Q 个询问，每行为 ci,di ，表示询问 ci 和 di 是否为亲戚。
输出格式
对于每个询问 ci,di，输出一行：若 ci 和 di 为亲戚，则输出Yes，否则输出No。
数据范围
1≤N≤20000,1≤M≤106,1≤Q≤106
输入样例：
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
输出样例：
Yes
No
Yes
1
2
3
二、解题报告
1、思路分析
（1）利用并查集，将所有互为亲戚的合并为同一个集合。
（2）通过查找两个结点的祖宗结点是否相同来判断两人是否为亲戚。
（3）并查集模板题，注意细节，并且此题使用cin、cout会超时，应使用scanf、printf或puts进行输入输出。
2、时间复杂度
时间复杂度为O(n)
3、代码详解
#include <iostream>
using namespace std;
const int N=20010;
int n,m;
int p[N]; //p[]存储每个结点的祖宗结点
//查找操作，返回x的祖宗结点
int find(int x){
if(p[x]!=x) p[x]=find(p[x]); //如果p[x]不是祖宗的话，递归查找x的祖宗
return p[x]; //直到找到x的祖宗，返回
}
int main(){
scanf("%d%d",&n,&m); //使用cin、cout会TLE
//初始化，每个结点的祖宗为自身
for(int i=1;i<=n;i++){
p[i]=i;
}
while(m--){
int a,b;
scanf("%d%d",&a,&b);
if(find(a)==find(b)) continue;
p[find(b)]=find(a); //a,b的祖宗结点不同，则合并
}
int q;
cin>>q;
while(q--){
int c,d;
scanf("%d%d",&c,&d);
if(find(c)==find(d)) puts("Yes"); //祖宗相同输出Yes，否则输出No
else puts("No");
}
return 0;
}
三、知识风暴
并查集
并查集主要用于处理一些不相交集合的合并问题。
具体操作可以参考我的这篇博客点击这里的“知识风暴”模块。
