并查集
在某些应用问题中,需要将n个不同的元素划分成一些不想交的集合。开始时,每个元素自成一个单元集合,然后按照一定的规律将归于同一组元素的集合进行合并操作。在此过程中需要反复对某个元素进行查询,判断其归属于哪个集合的运算操作,抽象出来的数据结构就叫做“并查集”。
其实,并查集是一种树形数据结构,只是我们是使用数组来表示树形的结构。总结上面的这一段概念,意思就是说并查集两个基本操作:1.查询一个元素在哪个集合;2.合并两个集合。
需要注意的是:初始化的数组上的元素都需要初始化成-1。原因是我们指定的规则是需要使用负数来代表根节点,负的这个数来代表自己集合中元素的个数;非负数则用来表示本元素的父节点元素的下标。参考下图。
此时假如进行合并操作,将1所在的集合合并到0所在的集合中,会发生这样的变化:
并查集的常规实现
以下给出实现并查集的常规代码。
public class UnionFindSet {
private int[] elem;
public UnionFindSet(int n){
this.elem = new int[n];
Arrays.fill(elem, -1);
}
//查找一个元素的根节点
public int findRoot(int x){
if(x < 0) return -1;
while(this.elem[x] >= 0){
x = this.elem[x];
}
return x;
}
//查找两个元素是否在同一个集合
public boolean isSameUnionFindSet(int x, int y){
int rootX = findRoot(x);
int rootY = findRoot(y);
if(rootX != -1 && rootY != -1 && rootX == rootY){
return true;
}
return false;
}
//集合合并操作
public void union(int x, int y){
int rootX = findRoot(x);
int rootY = findRoot(y);
if(rootX == -1 || rootY == -1 || rootX == rootY) return;
this.elem[rootX] += this.elem[rootY];
this.elem[rootY] = rootX;
}
//获取集合的数量
public int getCount(){
int cnt = 0;
for(int x : this.elem){
if(x < 0) cnt++;
}
return cnt;
}
}
并查集的简化实现(算法题 - 模板)
但是在算法题中,肯定不会按照上面这样子写的,因为这样的代码结构过于长。一般我们在做算法题的时候,都是提前把一些常用的模板默写下来,并查集也不例外。而这一版本的并查集会有一个新的规则,可以尽可能兼容同类型的算法题。
朴素的并查集
public class Main{
public int[] p = new int[N];
// 返回x的祖宗节点
public int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args){
// 初始化,假定节点编号是1~n
for(int i = 1; i <= n; i++) p[i] = i;
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
}
}
维护size的并查集
public class Main{
public int[] p = new int[N];
public int[] size = new int[N];
// 返回x的祖宗节点
public int find(int x){
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
public static void main(String[] args){
// 初始化,假定节点编号是1~n
for(int i = 1; i <= n; i++){
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合:
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
}
}
维护到祖宗节点的并查集
public class Main{
public int[] p = new int[N]; //存储每个点的祖宗节点
public int[] d = new int[N]; //存储当前点到祖宗节点的距离
// 返回x的祖宗节点
public int find(int x){
if (p[x] != x){
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}
public static void main(String[] args){
// 初始化,假定节点编号是1~n
for(int i = 1; i <= n; i++){
p[i] = i;
d[i] = 0;
}
// 合并a和b所在的两个集合:
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量
}
}