Luogu P3367 【模板】并查集

2018-06-17 22:01:47来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

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

输入输出格式

输入格式:

 

第一行包含两个整数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。

 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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1939 【模板】矩阵加速(数列)

下一篇:HDU 1575 Tr A(矩阵快速幂)