并查集在基础的合并与查询之上，还可以扩展为带权并查集（维护节点间关系）、可撤销并查集（支持回退）和按秩合并优化。本篇覆盖进阶用法与经典应用。
一、基础回顾
Mermaid · 渲染中（下方为源码）
graph LR A[并查集进阶] --> B[带权: 维护关系] A --> C[可撤销: 支持回退] A --> D[按秩合并]
int[] parent, rank;
void init(int n) {
parent = new int[n]; rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩
return parent[x];
}
void union(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank[rx] < rank[ry]) { int t = rx; rx = ry; ry = t; }
parent[ry] = rx;
if (rank[rx] == rank[ry]) rank[rx]++;
}二、带权并查集
维护每个节点到其根节点的"距离/关系"。
例题：食物链（POJ 1182）
三种动物 A、B、C 形成环形食物链。维护每个节点到根的偏移量（0=同类，1=吃父，2=被父吃）。
int[] parent, dist; // dist[x] = x 到 parent[x] 的关系
int find(int x) {
if (parent[x] != x) {
int root = find(parent[x]);
dist[x] = (dist[x] + dist[parent[x]]) % 3; // 路径压缩时累加
parent[x] = root;
}
return parent[x];
}
// 合并：x 对 y 的关系为 r（0=同类，1=x吃y，2=y吃x）
void union(int x, int y, int r) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
parent[rx] = ry;
dist[rx] = (dist[y] + r - dist[x] + 3) % 3;
}
// 查询：x 对 y 的关系
int query(int x, int y) {
if (find(x) != find(y)) return -1; // 不在同一集合
return (dist[x] - dist[y] + 3) % 3;
}