首页 > 代码库 > CODVES 5929 亲戚

CODVES 5929 亲戚

2024-09-14 10:10:55   213人阅读

5929 亲戚

时间限制: 1 s    空间限制: 128000 KB    题目等级 : 黄金 Gold题目描述 Description若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。 输入描述 Input Description第一行：三个整数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是否具有亲戚关系。输出描述 Output DescriptionP行，每行一个’Yes’或’No’。表示第i个询问的答案为“具有”或“不具有”亲戚关系。样例输入 Sample Input6 5 31 21 53 45 21 31 42 35 6样例输出 Sample OutputYesYesNo数据范围及提示 Data Size & Hint题目中已有，不重复解释。
技术分享
 1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4  5 const int MAXN=99999; 6 int n,m,dad[MAXN],a,b,c,d,q,r1,r2; 7  8 int find(int x) 9 {10     if(x!=dad[x]) dad[x]=find(dad[x]);11     return dad[x];12 }13 14 void unionn(int q,int p)15 {16     dad[r2]=r1;17 }18 19 int main()20 {21     cin>>n>>m;22     cin>>q;23     for(int i=1;i<=n;i++)24       dad[i]=i;25     for(int j=1;j<=m;j++){26         cin>>a>>b;27         r1=find(a);28         r2=find(b);29         if(r1!=r2)30         unionn(r1,r2);31     }32     for(int i=1;i<=q;i++){33         cin>>c>>d;34         if(find(c)==find(d))35         cout<<"Yes"<<endl;36         else37         cout<<"No"<<endl;38     }39     return 0;40 }
View Code

 

CODVES 5929 亲戚


联系
我们