并查集

并查集 顾名思义 就是对集合的合并和查询 可以在均摊 o1 的复杂度下解决此类问题

初始化

我们需要一个 father 数组 来记录各个元素所在集合 的 代表元素 假设我们有 n 个元素 从 1 开始 那么不妨如下初始化：

DSU(int n): father(n + 1)
{
	iota(all(father), 0ll);
}

int find(int x)

这个函数可以查询 x 所在的集合 其实就是查出 x 的代表元素 因此 有如下递归代码：

int find(int x)
{
	if (father[x] == x) return x;
	else
	{
		// 继续往上查找
		return find(father[x]);
	}
}

但是我们可以在这个步骤中增加一个记忆化的操作 也就是让 father[x] 直接等于 find(father[x]) 就得到了如下代码：

{
	return father[x] == x ? x : father[x] = find(father[x]);
}

bool issame(int i, int j)

这个函数可以查询 i， j 是否处于同一个集合 代码见下：

bool issame(int i, int j)
{
	return find(i) == find(j);
}

void merge(int i, int j)

这个函数可以合并 i 元素所在集合 和 j 元素所在集合 其实就是让 father[find(i)] = father[find(j)] 不妨用 rooti 表示 find(i) rootj 表示 find(j) 有如下代码：

void merge(int i, int j)
{
	auto ri = find(i), rj = find(j);
	if (ri == rj) return;
 
	parent[ri] = rj;
}

至此 最基本的合并查询功能我们就写完了。

---

拓展

在实际使用上 我们可能还想查询当前的集合数量 cnt 各个集合的大小 size[find(i)] 以及为了 find 递归时候降低复杂度 我们会选择 按秩合并

通俗来讲，就是比较两个集合哪个集合大 把小集合塞到大集合里 在实际实现上，会发现 father 的结构类似一棵树 我们通过把小树合并到大树上的做法 可以有效防止树退化成一条长链

因此 我们需要在初始化和 merge 函数中补充更多细节 代码见下：

初始化（完整版）

DSU(int n): parent(n + 1), size(n + 1, 1), count(n), rank(n + 1, 0)
{
	iota(all(parent), 0ll);
}

• parent[i] 记录元素 i 的父节点
• size[i] 记录以 i 为根的集合大小，初始化为 1
• count 记录当前集合的数量，初始为 n
• rank[i] 记录以 i 为根的树的高度（秩），初始化为 0

合并函数（完整版）

void merge(int i, int j)
{
	int ri = find(i), rj = find(j);
	if (ri == rj) return; // 已经在同一集合，无需合并
 
	// 按秩合并：让秩大的作为新的根
	if (rank[ri] < rank[rj]) swap(ri, rj);
 
	parent[rj] = ri; // 将 rj 的根指向 ri
	size[ri] += size[rj]; // 更新集合大小
 
	// 只有当两个秩相等时，新树的高度才会增加
	if (rank[ri] == rank[rj]) rank[ri]++;
 
	count--; // 集合数量减一
}

额外功能函数

// 获取元素 x 所在集合的大小
int getsize(int x)
{
	return size[find(x)];
}
 
// 获取当前集合的总数量
int getgroups()
{
	return count;
}

为什么只有秩相等时才 rank++？

• 当 rank[ri] > rank[rj] 时，将较矮的树合并到较高的树下，新树高度不变
• 当 rank[ri] == rank[rj] 时，两个等高的树合并，新树高度必然增加 1
• 这种策略保证了树的高度增长最慢，从而保持 find 操作的高效性

这是一个简单的 Python 示例，点击下方链接可以查看它的执行过程：