澳门太阳娱乐集团官网-太阳集团太阳娱乐登录

【太阳集团太阳娱乐登录】Luogu P3367 【模板】并
分类:脚本专栏

并查集

题目详见:[并查集] ()

这是一道裸的并查集题目(要不然叫模板呢) 废话不多说进入正题:

并查集通过一个一维数组来实现,本质上是维护一个森林。刚开始的时候,森林里的每一个结点都是一个集合(也就是只有一个结点的树),之后根据题意,逐渐将一个个集合合并(也就是合并成一棵大树)。之后寻找时不断查找父节点,当查找到父结点为本身的结点时,这个结点就是祖宗结点。合并则是寻找这两个结点的祖宗结点,如果这两个结点不相同,则任意将其中一边的集合作为另一边集合的子集。

AC代码:

#include<iostream>using namespace std;int n/*n个元素*/,m/*m个操作*/,f[10001]/*第i个人的祖宗为f[i]*/;int find(int x)            //找祖宗 {    if            //若自己的祖宗为自己       return f[x];              else                           return f[x]=find;//路径压缩:把递归过程中遇到的结点的祖宗结点也直接修改了 }void hebing(int x,int y)       //合并操作{    int fx=find,fy=find;    if                 //(其实这一步可有可无,因为之前已经判断过了)       f[fx]=fy;                //x的祖宗  的父亲  为y的祖宗     return;} int main(){    cin>>n>>m;    //读入    for(int i=1;i<=n;i++)    f[i]=i;                //初始化:n个数,每个数祖宗为自己     for(int i=1;i<=m;i++)  //依次读入m个操作要求    {        int z,x,y;        cin>>z>>x>>y;        if(z==2)           //执行查询操作         {            if==find //如果两个人为同一个祖宗,则在一个集合               cout<<"Y"<<endl;            else           //否则不在一个集合               cout<<"N"<<endl;        }        else               //执行合并操作           hebing;     }     return 0;}

题目描述

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

说明

时空限制: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=getchar13  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,r2=find;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{46         case 1:{47             unionn;48             break;49         }50         case 2:{51             if==find52             cout<<"Y"<<endl;53             else54             cout<<"N"<<endl;55             break;56         }        57     }    58 }59     return 0;60 }

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

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

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

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

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

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

输入输出格式

输入格式:

 

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

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

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

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

 

输出格式:

 

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

 

输入输出格式

输入格式:

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

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

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

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

输出格式:

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

说明

时空限制: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就可以啦,这就是一个非常简单的路径压缩啦

题目描述

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

输入输出样例

输入样例#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

输入输出样例

输入样例#1:

4 72 1 21 1 22 1 21 3 42 1 41 2 32 1 4

输出样例#1:

NYNY

本文由澳门太阳娱乐集团官网发布于脚本专栏,转载请注明出处:【太阳集团太阳娱乐登录】Luogu P3367 【模板】并

上一篇:MySQL 索引类型 下一篇:没有了
猜你喜欢
热门排行
精彩图文