代码模板-并查集

并查集用森林维护集合归属，f[x] 记 x 的父亲，根节点的父亲是自身。两种优化：路径压缩（查询时把路径上的点直接挂到根，常用）与启发式合并（小树并大树，带权并查集中常用）。

基本并查集（路径压缩）

const int N = 1e5 + 5;
int f[N], n;

void init() {                          // 初始化：每个元素自成一集合
    for (int i = 1; i <= n; i++) f[i] = i;
}

int get(int x) {                       // 查询（带路径压缩）
    return f[x] == x ? x : f[x] = get(f[x]);
}

void merge(int x, int y) {             // 合并
    f[get(x)] = get(y);
}

统计集合个数：数根节点个数，即 ans += (get(i) == i)，集合数 = ans（连通分量还需建的路 = ans - 1）。

带权并查集（维护节点到根的信息）

把信息记在节点到父亲的边上，路径压缩时累加。下面以维护「到根的距离」、集合大小记在根上为例（P1196 银河英雄传说）。

const int N = 30005;
struct node {
    int fa, d, size;      // fa: 父亲; d: 到根的距离; size: 集合大小（记在根上）
} f[N];

void init() {
    for (int i = 1; i <= N - 1; i++) f[i] = {i, 0, 1};
}

int get(int x) {
    if (f[x].fa == x) return x;
    int root = get(f[x].fa);
    f[x].d += f[f[x].fa].d;            // 路径压缩时累加距离
    return f[x].fa = root;
}

void merge(int x, int y) {             // 把 y 所在集合接到 x 所在集合后面（y 在后）
    int fx = get(x), fy = get(y);
    if (fx == fy) return;
    f[fy].d = f[fx].size;              // fy 到新根的距离 = 原 fx 集合大小
    f[fy].fa = fx;
    f[fx].size += f[fy].size;
}
// 查询 x、y 间隔：若 get(x) != get(y) 则不在同一集合；否则为 |d(x) - d(y)| - 1

拓展域并查集（维护多种关系）

把每个元素拆成多个域分别建并查集，空间 $O(nk)$ （ $k$ 为域数）。以食物链为例：原域、捕食域、天敌域共 3 倍空间。

const int N = 5e4 + 5;
int f[3 * N];

#define eat(x)   (x + N)       // 捕食域
#define eaten(x) (x + 2 * N)   // 天敌域

int get(int x) {
    return f[x] == x ? x : f[x] = get(f[x]);
}
void merge(int x, int y) {
    f[get(x)] = get(y);
}

// X、Y 同类：merge(x,y); merge(eat(x),eat(y)); merge(eaten(x),eaten(y));
// X 吃 Y：   merge(eat(x),y); merge(eaten(y),x); merge(eaten(x),eat(y));

相关笔记：【数据结构】并查集学习笔记