Luogu P3367 【模板】并查集
2018-06-27 10:02:47来源:未知 阅读 ()
题目描述
如题,现在有一个并查集,你需要完成合并和查询操作。
输入输出格式
输入格式:
第一行包含两个整数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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- C++ 模板类vector 2020-05-31
- C++ 模板类array 2020-05-31
- C++ 模板类vector 2020-05-30
- 单调队列模板【附例题】 2020-05-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash