并查集
- 将两个集合合并
- 询问两个元素是否在一个集合当中
基本原理: 每个集合用一颗树来表示, 树根的编号就是整个集合的编号. 每个节点存储它的父节点, p[x] 表示 x 的父节点.
① 如何判断树根
if(p[x]==x)② 如何求x的集合编号
while(p[x]!=x)x=p[x]③ 如何合并两个集合 p[x] 是 x 的集合编号, p[y] 是 y 的集合编号,
p[x]=y
优化: 路径压缩
普通并查集
//并查集模板
int p[N];
for(int i=1;i<=n;i++)p[i]=i; //初始化,假定节点编号是1~n
int find (int x) //返回x的祖宗节点 + 路径压缩
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
//合并a和b所在的两个集合
p[find(a)]=find(b)
维护size的并查集
//维护size的并查集模板
int p[N],size[N];
for(int i=1;i<=n;i++) //初始化,假定节点编号是1~n
{ //size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量
p[i]=i;
size[i]=1;
}
int find (int x) //返回x的祖宗节点 + 路径压缩
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
//合并a和b所在的两个集合
size[find(b)]+=size[find(a)];
p[find(a)]=find(b);
//注意:顺序不能调换
维护到祖宗节点距离的并查集
//维护到祖宗节点距离的并查集模板
int p[N],d[N]; //p[]存储每个点的祖宗节点,d[x]存储x到p[x]的距离
for(int i=1;i<=n;i++)p[i]=i;
int find (int x) //返回x的祖宗节点 + 路径压缩
{
if(p[x]!=x)
{
int u=find(p[x]);
d[x]+=d[p[x]];
p[x]=u;
}
return p[x];
}
//合并a和b所在的两个集合
p[find(a)]=find(b);
d[find(a)]=distance; //根据具体问题,初始化find(a)的偏移量
标签：int,查集,编号,集合,节点,size From： https://www.cnblogs.com/evilboy/p/17364334.html