Luogu P3367 【模板】并查集

题目描述

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

输入输出格式

输入格式：

第一行包含两个整数N、M，表示共有N个元素和M个操作。

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

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

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

输出格式：

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

输入输出样例

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

N
Y
N
Y

说明

时空限制：1000ms,128M

数据规模：

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

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

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

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5 int ret=0,ok=1;
 6 char ch=getchar();
 7 while(ch<'0'||ch>'9')
 8 {
 9 if(ch=='-')ok=-1;
10 ch=getchar();
11 }
12 for(;ch>='0'&&ch<='9';ch=getchar())
13  ret=ret*10+ch-'0';
14 return ret*ok;
15 }
16 int n,m,z,x,y; 
17 int father[10002];
18 inline int find(int i)
19 {
20     if(i==father[i])
21     return i;
22     while(i!=father[i])
23     i=father[i];
24     return father[i];
25 }
26 inline void unionn(int i,int j)
27 {
28     int r1=find(i),r2=find(j);
29     if(r1==r2)
30     return ;
31      father[r2]=r1;
32     father[j]=r1;
33     return ;
34 }
35 int main()
36 {
37 //freopen(".in","r",stdin);
38 //freopen(".out","w",stdout);
39 n=read(),m=read();
40 for(int i=1;i<=n;i++)
41 father[i]=i;
42 for(int i=1;i<=m;i++)
43 {
44     z=read(),x=read(),y=read();
45     switch(z){
46         case 1:{
47             unionn(x,y);
48             break;
49         }
50         case 2:{
51             if(find(x)==find(y))
52             cout<<"Y"<<endl;
53             else
54             cout<<"N"<<endl;
55             break;
56         }        
57     }    
58 }
59     return 0;
60 }

图论中的一个较经常考察的点：并查集。就是需要一个unionn(x,y)的合并问题和一个find(x)找父亲问题。

并查集首先就是先把自己指向自己做自己的父亲，等到后面找别人来做自己的父亲，一层一层上去，但是此题要注意的是路径压缩问题，路径没压缩的话就会3个点超时。

我们来平民化一下并查集的概念（很早以前从一个博客上看到的，我用自己的语言组织了一下）：

【平民化概念】：

在金庸小说的世界里，门派很多，经常会发生一些争斗，而且一般来说一个大的势力首先都需要自己出头来做老大，所以这个时候你自己的这个门派的老大就是你自己，即father[you]=you

后来，在你冒险的过程中你开始结识了一群很牛逼的好友，你觉得应该把他们拉到自己的门下，那么这个时候你就劝说他们把他们的门派老大指向你，意思就是说你是他们的老大，即father[别人]=you

但是你只是认识了这些比你低一级别的属下，你属下的属下和他属下的属下都互相不认识啊，这个时候就很容易起争端还不知道是自己人，互相打来打去（怎么这么傻），万一有一天在小树林里碰面，A、B二人都不知道对方是敌是友，如果要一级一级上报上去，显然是可以做到的，但是其中所耗费的时间必然是我们所比较不愿意接受的，所以我们希望我们属下的属下，他的老板就是我，意思就是说他可以直接认识我，并且接触到我，这样的话两人看到，就可能说：“在下是饕餮的属下”，“诶，我是Hammer他属下XX的属下，我们两个是朋友”然后两个人就手拉手一起走上人生巅峰了。。。。。这里的代码转换一下即：判断一下是敌是友（int x=find(A),y=find(B)解释：x是A的顶头上司，y是B的顶头上司)如果不认识，那么认识一个朋友就是一个保障嘛，那么这个时候：father[x]=y，但是你会发现如果这样，一层一层地上报岂不是很麻烦，那么你就可以直接father[A]=y就可以啦，这就是一个非常简单的路径压缩啦

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有