P1551 亲戚

admin

https://www.luogu.org/problemnew/show/P1551

题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述
规定：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个询问的答案为“具有”或“不具有”亲戚关系。

输入输出样例
输入样例#1：
6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6
输出样例#1：
Yes
Yes
No
说明
非常简单的并查集入门题哦！！！

zhwang

1. #include<stdio.h>
   
2. int f[10001],n,m,p;
   
3. int a[5001];
   
4. int b[5001];
   
5. int getf(int num)
   
6. {
   
7.     if(f[num]==num)
   
8.     {
   
9.         return num;
   
10.     }
    
11.     else
    
12.     {
    
13.         f[num]=getf(f[num]);
    
14.         return f[num];
    
15.     }
    
16. }
    
17. void bing(int father,int son)
    
18. {
    
19.     int t1=getf(father);
    
20.     int t2=getf(son);
    
21.     if(t1!=t2)
    
22.     {
    
23.         f[t2]=t1;
    
24.     }
    
25. }
    
26. int main()
    
27. {
    
28.     scanf("%d%d%d",&n,&m,&p);
    
29.     for(int i=1;i<=n;i++)
    
30.     {
    
31.         f[i]=i;
    
32.     }
    
33.     int x,y;
    
34.     for(int i=1;i<=m;i++)
    
35.     {
    
36.         scanf("%d%d",&x,&y);
    
37.         bing(x,y);
    
38.     }
    
39.     for(int i=1;i<=p;i++)
    
40.     {
    
41.         scanf("%d%d",&a[i],&b[i]);
    
42.     }
    
43.     for(int i=1;i<=p;i++)
    
44.     {
    
45.         if(getf(f[a[i]])==getf(f[b[i]]))
    
46.         {
    
47.             printf("Yes\n");
    
48.         }
    
49.         else
    
50.         {
    
51.             if(getf(f[a[i]])!=getf(f[b[i]]))
    
52.             {
    
53.                 printf("No\n");
    
54.             }
    
55.         }
    
56.     }
    
57.     return 0;
    
58. }

复制代码

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;
    
13. int x,y,n,m,t,fa[6000];
    
14. int getf(int u)
    
15. {
    
16.         if(u==fa[u])
    
17.                 return u;
    
18.         int f=getf(fa[u]);
    
19.         fa[u]=f;
    
20.         return f;
    
21. }
    
22. int main()
    
23. {  
    
24.         scanf("%d%d%d",&n,&m,&t);
    
25.         for(int i=1;i<=n;i++)
    
26.                 fa[i]=i;
    
27.         while(m--)
    
28.         {
    
29.                 scanf("%d%d",&x,&y);
    
30.                 int t1=getf(x),t2=getf(y);
    
31.                 if(t1!=t2)
    
32.                         fa[t1]=t2;
    
33.         }
    
34.         while(t--)
    
35.         {
    
36.                 scanf("%d%d",&x,&y);
    
37.                 if(getf(x)==getf(y))
    
38.                         printf("Yes\n");
    
39.                 else
    
40.                         printf("No\n");
    
41.         }
    
42.     return 0;
    
43. }

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m,p;
   
4. int a,b;
   
5. int father[5001];
   
6. int f(int x)
   
7. {
   
8.     while(father[x]!=father[father[x]])father[x]=father[father[x]];
   
9.     return father[x];
   
10. }
    
11. void merge(int x,int y)
    
12. {
    
13.     x=f(x);
    
14.     y=f(y);
    
15.     if(x==y)return;
    
16.     else father[y]=x;
    
17. }
    
18. void query(int x,int y)
    
19. {
    
20.     if(f(a)==f(b))cout<<"Yes";
    
21.         else cout<<"No";
    
22.         cout<<endl;
    
23. }
    
24. int main()
    
25. {
    
26.     cin>>n>>m>>p;
    
27.     for(int i=1; i<=n; i++)father[i]=i;
    
28.     for(int i=1; i<=m; i++)
    
29.     {
    
30.         cin>>a>>b;
    
31.         merge(a,b);
    
32.     }
    
33.     for(int i=1; i<=p; i++)
    
34.     {
    
35.         cin>>a>>b;
    
36.         query(a,b);
    
37.     }
    
38.     return 0;
    
39. }
    

复制代码

walk_alone

1. #include <cstdio>
   
2. int father[5001];
   
3. int getfather(int x)
   
4. {
   
5.         if(x!=father[x])
   
6.                 father[x]=getfather(father[x]);
   
7.         return father[x];
   
8. }
   
9. int main()
   
10. {
    
11.         int n,m,p,a,b;
    
12.         scanf("%d%d%d",&n,&m,&p);
    
13.         for(int i=1;i<=n;i++)
    
14.                 father[i]=i;
    
15.         for(int i=1;i<=m;i++)
    
16.         {
    
17.                 scanf("%d%d",&a,&b);
    
18.                 father[getfather(a)]=getfather(b);
    
19.         }
    
20.         for(int i=1;i<=p;i++)
    
21.         {
    
22.                 scanf("%d%d",&a,&b);
    
23.                 if(getfather(a)!=getfather(b))
    
24.                         printf("No\n");
    
25.                 else
    
26.                         printf("Yes\n");
    
27.         }
    
28.         return 0;
    
29. }

复制代码

liubo

1. #include<iostream>
   
2. using namespace std;
   
3. int p[5005];
   
4. int n,m,q;
   
5. int f(int i){
   
6.     return p[i] == i ? i : p[i] = f(p[i]);
   
7. }
   
8. void mer(int i,int j){
   
9.     int fi = f(i),fj = f(j);
   
10.     if(fi != fj)
    
11.         p[fi] = fj;
    
12.     return;
    
13. }
    
14. void ask(int i,int j){
    
15.     int fi = f(i),fj = f(j);
    
16.     if(fi == fj)
    
17.         cout << "Yes" << endl;
    
18.     else cout << "No" << endl;
    
19.     return;
    
20. }
    
21. int main(){
    
22.     cin >> n >> m >> q;
    
23.     for(int i = 1;i <= n;i++)
    
24.         p[i] = i;
    
25.     for(int i = 1;i <= m;i++){
    
26.         int x,y;
    
27.         cin >> x >> y;
    
28.         mer(x,y);
    
29.     }
    
30.     for(int i = 1;i <= q;i++){
    
31.         int x,y;
    
32.         cin >> x >> y;
    
33.         ask(x,y);
    
34.     }
    
35.     return 0;
    
36. }
    

复制代码

张笑宇

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m,p;
   
4. const int mx=5010;
   
5. int par[mx],i;
   
6. int getpar(int a)
   
7. {///找根节点
   
8.     if (par[a]!=a)
   
9.         par[a]=getpar(par[a]);
   
10.     return par[a];
    
11. }
    
12. int query(int a,int b)
    
13. {///查询a,b是否在同一个集合
    
14.     return getpar(a)==getpar(b);
    
15. }
    
16. void merge_(int a,int b)
    
17. {///合并a，b所在集合
    
18.     par[getpar(a)]=getpar(b);
    
19.     return;
    
20. }
    
21. int main()
    
22. {
    
23.     cin>>n>>m>>p;
    
24.     for (i=1;i<=n;i++) par[i]=i;
    
25.     for (i=1;i<=m;i++)
    
26.     {
    
27.         int a,b;
    
28.         cin>>a>>b;
    
29.         merge_(a,b);
    
30.     }
    
31.     for (i=1;i<=p;i++)
    
32.     {
    
33.         int a,b;
    
34.         cin>>a>>b;
    
35.         bool bb=query(a,b);
    
36.         if (bb==1) cout<<"Yes"<<endl;
    
37.         if (bb==0) cout<<"No"<<endl;
    
38.     }
    
39.     return 0;
    
40. }
    

复制代码

秀木于林

1. int getfather(int x)
   
2. {
   
3.         if(x!=father[x])
   
4.                 father[x]=getfather(father[x]);
   
5.         return father[x];
   
6. }

复制代码