标签：return px int bing 查集 find 数据结构 节点
并查集的使用范围:
1.合并集合
2.查询两元素是否属于同一集合
高级用法:
3.进行集合划分<带权并查集>
4.连通块块数查询&块内元素个数统计<连通图>
5.撤销合并<可持久化并查集> //本文暂不涉及, 我还不会
并查集基本操作:
#define rep(i,n) for(int i = 1; i <= n; i++) //简写for循环
class DisjointSet{
private:
int bing[Size];
public:
void init(int n);//初始化操作
int find(int x);//寻找父节点&路径压缩
void merge(int x, int y);//合并集合
bool same(int x, int y);//查询元素是否同属一个集合
};
初始化
void init(int n)
{
rep(i, n) bing[i] = i;//初始化,每个节点指向自己
}
寻找父节点&路径压缩
int find(int x)
{
if(bing[x] == x) return x;//根节点
return bing[x] = find(bing[x]);//路径压缩
}
合并集合
void merge(int x, int y)
{
int px = find(x);
int py = find(y);//寻找根节点
if(px == py) return;//同属一个集合
bing[px] = py;//集合合并
}
查询
bool same(int x, int y)
{
return find(x) == find(y);
}
并查集拓展操作_带权并查集
带权并查集的权重指代的是某一节点到集合中根节点的距离, 利用带权并查集可以实现二分图的划分, 和循环指向性集合的划分. 在维护过程中, 距离可以不为1.
class DisjointSet{
private:
int bing[Size];
int deep[Size];//距离根节点的距离
public:
void init(int n);
int find(int x);
bool merge(int x, int y, int distance);//distance指代的是x点到y点的距离
};
初始化
void init(int n)
{
rep(i, n)
{
bing[i] = i;
deep[i] = 0; //根节点的深度设定为0
}
}
寻找父节点&路径压缩
int find(int x)
{
if(bing[x] != x)
{
int t = bing[x]; //保证更新之后加上的节点仍为t
bing[x] = find(bing[x]);
deep[i] += deep[t]; //叠加权重
}
return bing[x];
}
合并集合
bool merge(int x, int y, int distance)
{
int px = find(x);
int py = find(y);
if(px == py)
{
if(deep[x] - deep[y] != distance) //若在同一集合且距离与给定值不同
return false;
}
else
{
bing[px] = py;
deep[px] = deep[y] - deep[x] + distance; //确定原根节点的权重
}
return true;
}
并查集的拓展操作_连通图
利用并查集, 可以获得所有节点的连通块个数以及每一个连通块的元素个数. 我们利用根节点记录连通块内的元素数量, 需要查询时, 直接查询根节点的数据即可.
class DisjointSet{
private:
int bing[Size];
int num[Size];//每一个连通块的数量
int lian;
public:
void init(int n);
int find(int x);
void merge(int x, int y);
int get_num(int x); //获得x元素所在的连通块内的元素个数
};
初始化
void init(int n)
{
rep(i, n)
{
bing[i] = i;
num[i] = 1;//未合并之前的块内元素为1
}
lian = n; //未合并之前的连通块数量为n
}
寻找父节点&路径压缩
int find(int x)//同最基础
{
if(bing[x] == x) return x;
return bing[x] = find(bing[x]);
}
合并集合
void merge(int x, int y)
{
int px = find(x);
int py = find(y);
if(px == py) return;
bing[px] = py;
num[py] += num[px];//将px所包含的元素个数都转移给py
lian--;//连通块的个数会因为合并而减少
}
获得元素个数
int get_num(int x)
{
return num[find(x)];//一定要注意是查找根节点的数据
}
标签：return,
px,
int,
bing,
查集,
find,
数据结构,
节点
From： https://www.cnblogs.com/slotifnotias/p/17742430.html