并查集

本篇将介绍并查集算法

并查集是一种用于管理元素集合的数据结构
实现为一个森林，每一棵树代表一个集合，树中的节点代表一个元素
顾名思义，并查集一共分为两个操作

  • 合并（union）：合并两棵树的根节点，相当于将两个集合合并为一个
  • 查询（find）：查询某个元素所属的树的根节点

初始化

初始时，需要给每个元素建立一个自己的树
也就是将自己的父节点设为自己

1
2
3
int fa[N]

for(int i = 1;i <= n;i++) fa[i] = i;

查询

循环向根节点爬，直到父节点指向自己的节点，当前节点就是根节点了

1
2
3
int find(int x){
	return fa[x] = x ? x : find(fa[x]);
}

这里可以进行优化，当我们查询过一次之后，可以将查询的结果赋值给原来的节点，使其直接连向根节点

1
2
3
int find(int x){
	return fa[x] = x ? x : fa[x] = find(fa[x]);
}

合并

合并两棵树，我们只需要将一个根节点连向另一个根节点即可

1
2
int x1,x2 //假设x1,x2为各自集合（树）的根节点
fa[x1] = x2