并查集
概述
并查集维护若干不相交集合，支持合并两个集合、查询元素所属集合两种操作。每个集合用一棵树表示，根作代表元，find 沿父指针上溯到根即可判断归属。配合路径压缩（查询时把路径上的点直接挂到根）与按秩合并两项优化，单次操作的均摊复杂度为反阿克曼函数级，近似常数，效率极高。给出结构体实现，含 init、find、merge、query 四个接口，并附判连通、种类并查集、带权并查集等例题，覆盖其常见变形与拓展用法。
参考资料
简介
并查集（Disjoint Set Union，DSU）维护若干不相交集合，支持合并两个集合、查询元素所属集合两种操作。每个集合用一棵树表示，根作为代表元，find 沿父指针上溯到根。配合 路径压缩（查询时把路径上的点直接挂到根）与 按秩合并，单次操作的均摊复杂度为反阿克曼函数 ，近似常数。
实现
struct DSU
{
int fa[N];
void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
int find(int u){return u==fa[u]?u:fa[u]=find(fa[u]);}
void merge(int u,int v){fa[find(u)]=find(v);}
bool query(int u,int v){return find(u)==find(v);}
};