华师一附中OI组

标题: P3367 【模板】并查集 [打印本页]

---

作者: admin    时间: 2018-7-27 22:42
标题: P3367 【模板】并查集
https://www.luogu.org/problemnew/show/P3367

题目描述
如题，现在有一个并查集，你需要完成合并和查询操作。

输入输出格式
输入格式：
第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

输入输出样例
输入样例#1：
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
输出样例#1：
N
Y
N
Y
说明
时空限制：1000ms,128M

数据规模：

对于30%的数据，N<=10，M<=20；

对于70%的数据，N<=100，M<=1000；

对于100%的数据，N<=10000，M<=200000。

---

作者: zhwang    时间: 2018-7-27 23:16

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

复制代码

---

作者: 吴语林    时间: 2018-7-28 07:44

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 n,t,o,x,y,fa[11000];
    
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",&n,&t);
    
25.         for(int i=1;i<=n;i++)
    
26.                 fa[i]=i;
    
27.         while(t--)
    
28.         {
    
29.                 scanf("%d%d%d",&o,&x,&y);
    
30.                 int f1=getf(x),f2=getf(y);
    
31.                 if(o==1)
    
32.                 {
    
33.                         if( f1 != f2 )
    
34.                                 fa[f1]=f2;
    
35.                 }
    
36.                 else
    
37.                 {
    
38.                         if(f1==f2)
    
39.                                 printf("Y\n");
    
40.                         else
    
41.                                 printf("N\n");
    
42.                 }
    
43.         }
    
44.         return 0;
    
45. }

复制代码

---

作者: 黄煦喆    时间: 2018-7-28 08:22

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

复制代码

---

作者: Chris_hhs    时间: 2018-7-29 17:51

1. #include<iostream>
   
2. using namespace std;
   
3. const int maxn=100000+2;
   
4. int fa[maxn];
   
5. int n,m;
   
6. int x,y,z;
   
7. int find(int x)
   
8. {
   
9.     if(fa[x]!=x) fa[x]=find(fa[x]);
   
10.     return fa[x];
    
11. }
    
12. int main()
    
13. {
    
14.     cin>>n>>m;
    
15.     for(int i=1; i<=n; i++) fa[i]=i;
    
16.     while(m--)
    
17.     {
    
18.         cin>>z>>x>>y;
    
19.         if(z==1)
    
20.         {
    
21.             int r1,r2;
    
22.             r1=find(x);
    
23.             r2=find(y);
    
24.             fa[r1]=r2;
    
25.         }
    
26.         if(z==2)
    
27.         {
    
28.             if(find(x)==find(y)) cout<<"Y";
    
29.             else cout<<"N";
    
30.             cout<<endl;
    
31.         }
    
32.     }
    
33.     return 0;
    
34. }
    

复制代码

---

作者: walk_alone    时间: 2018-7-29 19:05

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

复制代码

---

作者: 张笑宇    时间: 2018-7-30 09:32

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

复制代码

---

作者: Scorpio    时间: 2018-7-31 11:51

1. #include<iostream>
   
2. using namespace std;
   
3. int f[10500];
   
4. int n,m,i,z,x,y;
   
5. int findhhh(int x)
   
6. {
   
7.     int r=x,i=x,j;
   
8.     while(f[r]!=r)
   
9.         r=f[r];
   
10.     while(i!=r)
    
11.     {
    
12.         j=f[i];
    
13.         f[i]=r;
    
14.         i=j;
    
15.     }
    
16.     return r;
    
17. }
    
18. void join(int x,int y)
    
19. {
    
20.     int fx,fy;
    
21.     fx=findhhh(x);
    
22.     fy=findhhh(y);
    
23.     if(fx!=fy)
    
24.         f[fx]=fy;
    
25. }
    
26. string findxy(int x,int y)
    
27. {
    
28.     int fx,fy;
    
29.     fx=findhhh(x);
    
30.     fy=findhhh(y);
    
31.     if(fx==fy)
    
32.         return "Y";
    
33.     else
    
34.         return "N";
    
35. }
    
36. int main()
    
37. {
    
38.     cin>>n>>m;
    
39.     for(i=1;i<=10500;i++)
    
40.         f[i]=i;
    
41.     for(i=1;i<=m;i++)
    
42.     {
    
43.         cin>>z>>x>>y;
    
44.         if(z==1)
    
45.             join(x,y);
    
46.         else
    
47.             cout<<findxy(x,y)<<endl;
    
48.     }
    
49.     return 0;
    
50. }
    

复制代码

---

作者: ZMQ    时间: 2018-8-6 21:58
提示: 作者被禁止或删除 内容自动屏蔽

---

作者: 倚窗倾听风吹雨    时间: 2018-9-19 19:09

1. #include<iostream>
   
2. using namespace std;
   
3. const int N=10010;
   
4. int a[N],n,m,x,y,z;
   
5. int getf(int q)
   
6. {
   
7.     if(a[q]==q)return q;
   
8.     a[q]=getf(a[q]);
   
9.     return a[q];
   
10. }
    
11. void merge2(int q,int w)
    
12. {
    
13.     int t1,t2;
    
14.     t1=getf(q);
    
15.     t2=getf(w);
    
16.     if(t1!=t2)
    
17.         a[t2]=t1;
    
18.     return;
    
19. }
    
20. int main()
    
21. {
    
22.     cin>>n>>m;
    
23.     for(int i=1;i<=n;i++)a[i]=i;
    
24.     for(int i=1;i<=m;i++)
    
25.     {
    
26.         cin>>z>>x>>y;
    
27.         if(z==1)merge2(x,y);
    
28.         if(z==2)
    
29.             if(getf(x)==getf(y))cout<<'Y'<<endl;
    
30.             else cout<<'N'<<endl;
    
31.     }
    
32.     return 0;
    
33. }
    

复制代码

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2