并查集

主要用于快速判断两个元素是否属于同一个集合，主要有两个操作

• 查找，find(x)，判断 x 属于哪个集合
• 合并，Union(x, y)，合并 x，y 所在的两个集合

（可恶，小时候在 CSDN 上好像还写过并查集笔记）

核心思路

朴素的，我们确乎是可以使用一个向量 / 集合来描述整个集合，不过问题在于合并的时候非常贵，因为需要移动大量元素（如果还设计扩容什么那就更坏了）

然而对于一个集合其实并不需要真的关心其内部关系，所以思路换成为每一个集合选取一个代表元素，然后维护整个森林结构，森林中的每一棵树代表一个集合，每一棵树的根节点就是集合的代表元素

对于元素的查询，只需要判断他们的代表元素是否一致即可；在合并的时候也只需要把其中一方的代表元素接到另一颗树上即可，非常的方便

路径压缩

上文已经提到，我们其实不需要关心一个集合的内部连接关系，所以对于元素 x

x -> a -> b -> root
x -> root

两种连接是等价的

那么在一次 find 操作中， 我们既然已知了 x 的 root，那么不妨直接在查找的时候把顺路的节点全部连到 root 上，减少其深度

实现

也就是我们仅需要维护一个 parent[N] 的数组，存储每一个元素的父亲是谁，对于根节点，它的成立条件为 parent[root] = root

int find(int x)
{
    if (parent[x] != x)
        parent[x] = find(parent[x]);

    return parent[x];
}

带路径压缩的查找版本，如果不需要路径压缩即把赋值操作换成返回即可

bool unite(int x, int y)
{
	int rootX = find(x);
	int rootY = find(y);

	if (rootX == rootY)
		return false;

	if (size[rootX] < size[rootY])
		std::swap(rootX, rootY);

	parent[rootY] = rootX;
	size[rootX] += size[rootY];

	return true;
}

此处额外维护了一个 size 数组，用于判断一个集合的大小，这样在合并的时候 —— 可以把小树挂在大树下，以减小深度，即常说的“按秩合并”

在上述的实现下，其查找和合并操作的均摊复杂度为

$$O(\alpha (N))$$

约为 O(1)

不过值得注意的，我们难以维护“删除”相关的操作 —— 主要原因是丢失了原始连接关系

以及如果需要知道两个元素的相对关系，可以维护一个带权的并查集（