首页 > 代码库 > 洛谷p3367 并查集模板
洛谷p3367 并查集模板
并查集是一种树型的数据结构，主要用来处理一些不相交集合的合并和更改问题。
比如找4的祖先，原来是 4->2->1，通过并查集路径压缩后，变为 4->1。也就变成了下图。
并查集的模板题：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int dad[2000001];
int find(int x)//很简单的find函数，网上还有while版本的，手懒没抄= =
{
return dad[x]==x?x:dad[x]=find(dad[x]);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i)dad[i]=i;
for(int i=1;i<=m;++i)
{
int x,y,z;
scanf("%d%d%d",&z,&x,&y);
int X=find(x);
int Y=find(y);
if(z==1)
{
if(X!=Y)
{
dad[X]=Y;
}
}
else
{
if(X==Y) printf("Y\n");
else printf("N\n");
}
}
return 0;
}
按秩合并：
x=find(x); y=find(y) if(deep[x])>deep[y]) swap(x,y);//保证y的深度一定大于x dad[x]=y; deep[y]=max(deep[y],deep[x]+1);
洛谷p3367 并查集模板
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。