并查集的概念与应用

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。 基本的并查集支持两种操作： Union：合并两个元素所属集合（即合并对应的树） Find：查询某个元素所属集合（即对应的树的根节点），用于判断两个元素是否属于同一集 合 —— 引用自 OI Wiki

使用并查集，可以很好地查询连通块数量以及合并连通块。

并查集的简单实现

初始化

初始时，每个元素都位于一个单独的集合，表示为一棵只有根节点的树。方便起见，我们将根节点的父亲设为自己。

#define MAX_SIZE 200

int father[MAX_SIZE];

void build(int n) { // 可以把 n 填在外面
	for (int i = 0; i < n; i++) {
		father[i] = i; // 将根节点的父亲设为自己
	}
}

查询元素所在集合

我们需要沿着树向上移动，直至找到根节点。

int find(int x) { // 返回根节点
	return father[x] == x ? x : find(father[x]); // 递归地向上寻找
}

为优化后续查询，我们可以采用路径压缩，即将查询过程中经过的每个元素都直接连至根节点。

int find(int x) { // 返回根节点
	return father[x] == x ? x : father[x] = find(father[x]);
	// 递归地向上寻找，并且在这个过程中将经过节点连至根节点
}

合并

要合并两棵树，我们只需要将一棵树的根节点连到另一棵树的根节点。

void unite(int x, int y) {
	father[find(x)] = find(y); // x 所在的根节点连至 y 的根节点
}