题目描述：
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
规定：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，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出：
P行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。
讲解： 这是一场简单的找 father 的游戏，如果两个小伙伴，有一个共同的爹，他们两个就有亲戚关系了；也反映出了，并查集在解决问题方面的巨大潜能；
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cstdlib> 5 using namespace std; 6 int father[50002],a,b,m,n,p; 7 int find(int x){ 8 if (father[x]!=x){ //如果自己还是自己的爹，直接返回,否则找到最终的父亲，当成自己的爹 9 //cout<<"儿子 "<<father[x]<<endl; 10 father[x]=find(father[x]); 11 } 12 return father[x]; 13 } 14 int main(){ 15 scanf("%d%d%d",&n,&m,&p); 16 for (int i=1;i<=n;i++) father[i]=i;//为每个人都建立一个数组； 17 for (int i=1;i<=m;i++){ 18 scanf("%d%d",&a,&b); 19 a=find(a),b=find(b); 20 cout<<a<<"->"<<b<<endl; 21 father[a]=b; 22 } 23 for(int i=1;i<=p;i++){ 24 // cout<<"start"<<endl; 25 scanf("%d%d",&a,&b); 26 a=find(a);b=find(b); //各找个的爹 27 if(a==b)printf("Yes\n");else printf("No\n"); 28 // cout<<"END"<<endl; 29 } 30 return 0; 31 }
一个找亲戚游戏，引发了一场算法的学习——并查集,布布扣,bubuko.com
原文：http://www.cnblogs.com/lovychen/p/3674593.html