09 带移动和删除的并查集 ★★★☆☆

普通并查集只能把整个集合合并，无法把单个元素从集合中「删除」或「移动」到另一个集合——因为一个节点可能是别人的父亲，直接摘掉会破坏树结构。用「虚拟节点」技巧可以  完成删除和移动。

Tips：部分内容由 AI 生成，如发现问题请在评论区留言。

一、为什么不能直接删除/移动

普通并查集里，每个元素就是树中的一个节点，节点可能有孩子。若想「删除 x」，把 fa[x] 改成别的并不管用——x 的孩子们仍指向 x，根本无法把它单独摘出来，也无法干净地「移动」到别的集合。

二、核心技巧：虚拟节点

思路：给每个真实元素分配一个虚点，并查集只在虚点上操作，用 id[x] 记录元素 x 当前对应的虚点。

• • 初始：id[x] = x，每个元素对应编号相同的虚点。
• • 删除 x：给 x 换一个新虚点 id[x] = ++tot，x 变成孤立点；旧虚点仍留在原集合，不影响其它元素。
• • 移动 x 到 y 的集合：先删除 x（换新虚点），再 union(id[x], id[y])。

模板：

const int N = 100005;   // 真实元素个数const int Q = 100005;   // 最多删除/移动操作次数int fa[N + Q];          // 虚点并查集，容量 = 元素数 + 操作数int id[N];              // id[x]：元素 x 当前对应的虚点int tot;                // 已分配的最大虚点编号void init(int n){    tot = n;    for (int i = 1; i <= n; i++) id[i] = i;    for (int i = 1; i <= n + Q; i++) fa[i] = i;}int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }void erase(int x){ id[x] = ++tot; }   // 删除：换新虚点（fa[tot] 已在 init 初始化为 tot）void move(int x, int y){              // 移动：删 + 并    erase(x);    fa[find(id[x])] = find(id[y]);}void merge(int x, int y){    int fx = find(id[x]), fy = find(id[y]);    if (fx != fy) fa[fx] = fy;}

每次删除/移动会新增一个虚点，所以 fa[] 要开到「元素数 + 操作数」那么大。旧虚点不能删掉也不能复用——它代表原集合里剩余的元素。

三、带删除：HDU 2473 Junk-Mail Filter （洛谷：SP5150）

题意：n 个元素（编号 0 ~ n-1），m 个操作：M x y 合并 x、y；S x 把 x 从当前集合中删除（孤立）。最后输出剩余的不同集合个数。

思路：删除就是给 x 换一个新虚点。最后把所有元素的 find(id[i]) 去重计数即可。

#include <cstdio>#include <set>using namespace std;const int N = 100005;int fa[2 * N], id[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }int main(){    int n, m, kase = 0;    while (~scanf("%d%d", &n, &m) && (n || m)) {        int tot = n;        for (int i = 0; i < n; i++) fa[i] = i, id[i] = i;        while (m--) {            char op; scanf(" %c", &op);            if (op == 'M') {                int x, y; scanf("%d%d", &x, &y);                int fx = find(id[x]), fy = find(id[y]);                if (fx != fy) fa[fx] = fy;            } else {                int x; scanf("%d", &x);                id[x] = ++tot;                fa[id[x]] = id[x];   // 新虚点自成一个集合            }        }        set<int> roots;        for (int i = 0; i < n; i++) roots.insert(find(id[i]));        printf("Case #%d: %d\n", ++kase, (int)roots.size());    }    return 0;}

四、带移动：UVA 11987 Almost Union-Find

题意：n 个元素（编号 1 ~ n，元素值 = 编号），m 个操作：

• • 1 p q：合并 p、q 所在集合；
• • 2 p q：把 p 移到 q 所在集合；
• • 3 p：输出 p 所在集合的元素个数与元素值之和。

思路：移动时除了换虚点，还要维护每个集合根的 cnt（大小）和 sum（和）：p 从旧集合扣除、并入新集合。

#include <cstdio>using namespace std;const int N = 100005;int fa[2 * N], cnt[2 * N];long long sum[2 * N];int id[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }int main(){    int n, m;    while (~scanf("%d%d", &n, &m)) {        int tot = n;        for (int i = 1; i <= n; i++) {            fa[i] = i; cnt[i] = 1; sum[i] = i;   // 元素值 = 编号            id[i] = i;        }        while (m--) {            int op; scanf("%d", &op);            if (op == 1) {                       // 合并 p、q                int p, q; scanf("%d%d", &p, &q);                int fp = find(id[p]), fq = find(id[q]);                if (fp != fq) { fa[fp] = fq; cnt[fq] += cnt[fp]; sum[fq] += sum[fp]; }            } else if (op == 2) {                // 移动 p 到 q 的集合                int p, q; scanf("%d%d", &p, &q);                int fp = find(id[p]), fq = find(id[q]);                if (fp != fq) {                    cnt[fp]--; sum[fp] -= p;     // p 从旧集合扣除                    id[p] = ++tot;               // 新虚点                    fa[id[p]] = id[p];                    cnt[id[p]] = 1; sum[id[p]] = p;                    fa[id[p]] = fq;              // 并入 q 的集合                    cnt[fq]++; sum[fq] += p;                }            } else {                             // 查询 p 所在集合                int p; scanf("%d", &p);                int fp = find(id[p]);                printf("%d %lld\n", cnt[fp], sum[fp]);            }        }    }    return 0;}

五、进阶 CF1725K Kingdom of Criticism

题意：维护长度为 n 的序列，q 次操作：

• • 1 k w：把第 k 个数改成 w；
• • 2 k：输出第 k 个数；
• • 3 l r：把值落在  内的所有位置，改成  或 （靠近哪个改哪个， 为奇数保证唯一）。

思路：把「虚点」从"位置"推广到"值"——每个出现过的值建一个虚点，每个位置指向它当前值对应的虚点。单点修改就是给位置换一个新身份节点并指向新值；操作 3 用 map 按值找出  内的所有虚点，分别并入 、 的集合。

#include <bits/stdc++.h>using namespace std;const int N = 2500005;int fa[N], val[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }int main(){    ios::sync_with_stdio(false); cin.tie(nullptr);    int n; cin >> n;    vector<int> id(n + 1);    map<int,int> mp;                    // 值 -> 虚点    int tot = 0;    auto getNode = [&](int v) {         // 取/新建 值为 v 的虚点        auto it = mp.find(v);        if (it != mp.end()) return it->second;        int u = ++tot; fa[u] = u; val[u] = v;        mp[v] = u;        return u;    };    for (int i = 1; i <= n; i++) {        int x; cin >> x;        id[i] = ++tot; fa[id[i]] = getNode(x);    }    int q; cin >> q;    while (q--) {        int op; cin >> op;        if (op == 1) {            int k, w; cin >> k >> w;            id[k] = ++tot; fa[id[k]] = getNode(w);   // 换身份节点 = 移动        } else if (op == 2) {            int k; cin >> k;            cout << val[find(id[k])] << '\n';        } else {            int l, r; cin >> l >> r;            int m = (l + r) >> 1;            vector<int> roots;            for (auto it = mp.lower_bound(l); it != mp.end() && it->first <= r; )                roots.push_back(it->second), it = mp.erase(it);            for (int root : roots) {                int t = (val[root] <= m) ? (l - 1) : (r + 1);                int fr = find(root), ft = find(getNode(t));                if (fr != ft) fa[fr] = ft;            }        }    }    return 0;}

只是多了一步按值域批量合并，复杂度 。

六、树上删除（离线倒序）P4092 [HEOI2016/TJOI2016] 树

题意：一棵以 1 为根的树，初始只有结点 1 有标记。两种操作：C x 给 x 打标记；Q x 询问 x 最近的有标记祖先（含 x 自己）。

思路：换个思路——离线倒序。正向"加标记"难处理，倒过来"加标记"就变成"取消标记"，而并查集"删标记"很容易：把该点的 fa 从"指向自己"改回"指向父亲"。

并查集含义是"跳到最近的标记祖先"：有标记的点 fa[x] = x，无标记的点 fa[x] = 父节点，find(x) 一路压缩跳到最近的标记点。

#include <bits/stdc++.h>using namespace std;const int N = 100005;vector<int> g[N];int fa[N], f[N], cnt[N];int op[N], x[N];int find(int x){ return fa[x] == x ? x : fa[x] = find(fa[x]); }void dfs(int u, int p){    f[u] = p;    for (int v : g[u]) if (v != p) dfs(v, u);}int main(){    ios::sync_with_stdio(false); cin.tie(nullptr);    int n, q; cin >> n >> q;    for (int i = 1; i < n; i++) {        int u, v; cin >> u >> v;        g[u].push_back(v);        g[v].push_back(u);    }    dfs(1, 1);                          // 求每个点的直接父亲    for (int i = 1; i <= q; i++) {        char c; cin >> c >> x[i];        op[i] = (c == 'C');        if (op[i]) cnt[x[i]]++;         // 统计每个点被标记的次数    }    cnt[1] += 1;                        // 根节点初始就带一个标记    for (int i = 1; i <= n; i++)        fa[i] = (cnt[i] > 0) ? i : f[i]; // 有标记指向自己，无标记指向父亲    vector<int> ans;    for (int i = q; i >= 1; i--) {        if (op[i]) {                    // 倒序：C 变成取消标记            if (--cnt[x[i]] == 0) fa[x[i]] = f[x[i]];        } else {                        // Q：最近标记祖先            ans.push_back(find(x[i]));        }    }    reverse(ans.begin(), ans.end());    for (int v : ans) cout << v << '\n';    return 0;}

同类型的还有 P1197 星球大战；P3273 [SCOI2011] 棘手的操作 是"并查集 + 左偏树 + 单点删除"的进阶题。

七、总结

• • 普通并查集无法单独删除/移动元素，用虚拟节点技巧解决。
• • 每个元素通过 id[x] 映射到虚点，删除/移动就是给元素换一个新虚点，旧虚点留在原集合。
• • 删除/移动 ，find/merge 复杂度同普通并查集。
• • 数组要开「元素数 + 删除/移动次数」，旧虚点不可复用。