Disjoint Set Union

并查集可以用来维护一类具有传递性的关系，维护形如将 \(x\) 与 \(y\) 所在集合合并和询问 \(x\) 和 \(y\) 是否在同一个集合的操作。

对于普通并查集来说，有路径压缩和按秩合并等优化，路径压缩一般实现如下 ：

按秩合并则取点数小的连向点数大的即可。