「CODEVS1073」亲戚(家族)
题目描述
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易。现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：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个询问的答案为“具有”或“不具有”亲戚关系。
样例输入
|
1 2 3 4 5 6 7 8 9 |
6 5 3 1 2 1 5 3 4 5 2 1 3 1 4 2 3 5 6 |
样例输出
|
1 2 3 |
Yes Yes No |
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> using namespace std; int father[20001]; int m,n,i,x,y,q; int find(int x)//用于查找一个元素的所在集合即根节点 { if(father[x]!=x) father[x]=find(father[x]);//路径压缩，递归将路径上的元素父亲指针都指向根节点 return father[x]; } void u(int r1,int r2)//合并两个集合 { father[r2]=r1; } int main() { cin>>n>>m>>q; for(i=1;i<=n;i++) father[i]=i;//初始每个元素的父亲指针指向本身 for(i=1;i<=m;i++) { cin>>x>>y; int r1=find(x); int r2=find(y); if(r1!=r2)u(r1,r2);//合并两个元素的根节点 } for(i=1;i<=q;i++) { cin>>x>>y; if(find(x)==find(y))cout<<"Yes"<<endl;//判断两个元素的所在集合即根节点是否相同 else cout<<"No"<<endl; } return 0; } |
Subscribe
计数器 9824577
OI 课件=>
OI 课件=>