什么是并查集？可以近似地用数学的观点来看，就像数学中的集合一般。但是并不尽相同，并查集在维基百科中的定义如下：

在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。

既然名字叫并查集，那么肯定有其原因，因为此数据结构中的两个操作便是并和查。

  • Find【查】：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union【并】：将两个子集合并成同一个集合。

初始化并查集

我们可以使用两个数组来简单地实现并查集：

1
2
3
4
#define MAX_N 10000

int par[MAX_N];		// 父亲
int rank[MAX_N];	// 树高

有了以上定义，便可以实现并查集的初始化：

1
2
3
4
5
6
void init(int n) {
	for (int i = 0; i < n; i++) {
		par[i] = i;
		rank[i] = 0;
	}
}

并查集 —— 查

  • 由于 par[] 数组储存的就是父节点下标，所以依次上诉，直至 par[i]=i
  • 在上寻过程中，可进行路径压缩，也就是将查找的结点直接挂接在根结点上
1
2
3
4
5
6
7
8
// 查询树的根
int find(int x) {
	if (par[x] == x) {
		return x;
	} else {
		return par[x] = find(par[x]);
	}
}

并查集 —— 并

  • 合并过程需要依次上溯，直至到根节点，然后比较二者所属集合的树高，将低的一方挂接在高的一方即可【这是为了使树相对平衡】。
1
2
3
4
5
6
7
8
9
10
11
12
13
// 合并x和y所属的集合
void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)	return;
	
	if (rank[x] < rank[y]) {
		par[x] = y;
	} else {
		par[y] = x;
		if (rank[x] == rank[y])	rank[x]++;
	}
}