并查集Disjoint-set union

维护动态合并的互不相交集合。

常见操作#

n 为元素数，α 为反阿克曼函数；采用按秩 / 大小合并和路径压缩。

操作	时间复杂度	条件与说明
初始化 n 个独立集合	$O(n)$	创建父节点与秩或大小数组。
查找代表元	摊还 $O(\alpha(n))$	这是操作序列上的界；不能解读为每次操作的确定性常数上界。
合并 / 判断同一集合	摊还 $O(\alpha(n))$	先找代表元，再按秩或大小链接根。
列出所有分组	$O(n\alpha(n))$	逐元素找代表元再分桶；输出至少 $O(n)$ 。
拆分集合 / 删除连接	基本结构不支持	动态连通性、回滚并查集等是不同扩展，不能用 union 操作逆向撤销一般合并。

仅路径压缩或仅按秩合并时，需使用相应的独立分析。

基础原理参考资料

AtCoder Library · DSU合并、代表元、连通判断与按组枚举的摊还成本。