【模板】并查集 题解

思路

子任务 1：仅有查询

没有合并操作时，每个元素始终独立成集。因此询问 $(x,y)$ 的答案仅取决于 $x=y$，逐条直接判断即可，时间复杂度为 $O(M)$，空间复杂度为 $O(1)$。

子任务 2：合并全部在查询之前

把前缀中的合并操作看成无向边。由于开始查询后不再增加边，可以先遍历该图，给每个连通分量染上编号，再用编号是否相同回答所有查询。时间复杂度为 $O(N+M)$，空间复杂度为 $O(N+M)$。

做法

用并查集维护当前集合。find(x) 返回 $x$ 所在集合的代表元，并在递归返回时进行路径压缩；合并两个集合时，把较小集合的根挂到较大集合的根上。

正确性证明

初始时每个结点的父亲是自身，恰好表示每个元素各自成集。

对操作序列归纳。若当前操作是合并，设两个元素的代表元分别为 $r_x,r_y$。二者相同时集合关系不变；否则连接两个根，恰好把这两个集合合并，其他集合不受影响。若当前操作是查询，两个元素属于同一集合当且仅当它们沿父指针到达同一个根，因此比较两个代表元所得的 Y 或 N 正确。路径压缩和按大小合并只改变表示树的形状，不改变集合划分。

故算法对全部操作均给出正确答案。

复杂度

使用路径压缩和按大小合并后，每次操作的均摊时间复杂度为 $O(\alpha(N))$，总时间复杂度为 $O((N+M)\alpha(N))$，空间复杂度为 $O(N)$。