如何正确实现不相交集合（Disjoint Set）的拆分操作？

云原生阿岚

2026-6-24

问题描述

我正在开发一个支持以下操作的无向图：

addPerson：插入节点person。
addRelation：添加id1与id2之间的边。
modifyRelation：修改/移除id1与id2之间的边。
isCircle：检查id1与id2是否连通。
queryBlockSum：查询可划分的不相交集合数量。

对应的Java实现片段：

public class MyNetwork implements Network {
    /* ... */
    private final DisjointSet disjointSet;

    @Override
    public void addPerson(Person person) {
        /* ... */
        disjointSet.add(person.getId());
    }

    @Override
    public void addRelation(int id1, int id2, int value) {
        /* ... */
        disjointSet.merge(id1, id2);
    }

    @Override
    public void modifyRelation(int id1, int id2, int value) {
        /* ... */
        int parent = disjointSet.find(id1);
        if (/* 应移除边 */) {
            HashSet<Integer> set1 = /* 所有与id1连通的节点 */;
            HashSet<Integer> set2 = /* 所有与id2连通的节点 */;
            if (!set1.contains(parent)) {
                disjointSet.resetParent(set1, parent, id1);
            }
            if (!set2.contains(parent)) {
                disjointSet.resetParent(set2, parent, id2);
            }
        }
    }

    @Override
    public boolean isCircle(int id1, int id2) {
        return disjointSet.find(id1) == disjointSet.find(id2);
    }

    @Override
    public int queryBlockSum() {
        return disjointSet.getSetCount();
    }
}

为提升效率，我实现了不相交集合（Disjoint Set）数据结构，支持以下操作：

add：添加元素x。
find：查找元素x的父节点（带路径压缩）。
merge：合并两个集合x与y。
split：将集合c中所有元素的父节点从oldParent改为newParent，将一个集合拆分为两个。（确保c中任意元素x满足find(x) == oldParent）
getSetCount：获取集合数量。

对应的DisjointSet实现：

public class DisjointSet {
    private final HashMap<Integer, Integer> parent;
    private int setCount;

    public DisjointSet() {
        this.parent = new HashMap<>();
        this.setCount = 0;
    }

    public int getSetCount() {
        return setCount;
    }

    public void add(int x) {
        parent.put(x, x);
        setCount++;
    }

    public int find(int x) {
        int parentX = parent.get(x);
        if (parentX == x) {
            return x;
        }
        parentX = find(parentX);
        parent.put(x, parentX);
        return parentX;
    }

    public boolean merge(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);
        if (parentX != parentY) {
            parent.put(parentX, parentY);
            setCount--;
            return true;
        }
        return false;
    }

    public void split(Collection<Integer> c, int oldParent, int newParent) {
        for (Integer x : c) {
            parent.put(x, newParent);
        }
        setCount++;
    }
}

遇到的问题

多次合并与拆分后，不相交集合出现异常：本该处于同一集合的两个元素，实际父节点不同，导致判定不连通。

我尝试先对要拆分的集合c中的元素执行find再修改父节点，但无效：

public void split(Collection<Integer> c, int oldParent, int newParent) {
    // 无法修复bug
    for (Integer x : c) {
        find(x);
    }
    for (Integer x : c) {
        parent.put(x, newParent);
    }
    setCount++;
}

但如果在拆分前对所有元素执行find，bug就被修复了：

public void split(Collection<Integer> c, int oldParent, int newParent) {
    // 可修复bug
    for (Integer x : parent.keySet()) {
        find(x);
    }
    for (Integer x : c) {
        parent.put(x, newParent);
    }
    setCount++;
}

我不理解为何需要更新所有元素的父节点，即使它们不需要被拆分。请问正确的不相交集合拆分操作实现方式是什么？或者是否必须重建不相交集合，因为它根本不支持拆分？

问题分析与解决方案

为什么全量执行`find`能修复bug？

你的DisjointSet使用了路径压缩优化，这会让部分元素的父节点直接指向根节点，但还有一些未被访问过的元素，它们的父节点可能还是中间节点，而非当前集合的根。

当执行拆分操作时，假设原集合根是oldParent，你要把c中的元素移到newParent下。如果存在一些不在c中的元素，它们的父节点是c中的某个元素（而非oldParent），此时只修改c中元素的父节点为newParent，这些不在c中的元素的父链就会指向newParent所在的新集合，而它们本应该留在原集合（属于oldParent）。

举个例子：

原结构：A -> B -> oldParent，其中A不在拆分集合c里，B在c里。
只对c中的B执行find，B会直接指向oldParent，修改B的父节点为newParent后，A的父节点还是B，导致A被错误划分到newParent的集合中。
对所有元素执行find，A会直接指向oldParent，此时修改B的父节点为newParent，A的父节点依然是oldParent，不会被错误拆分。

不相交集合（DSU）的本质限制

标准的DSU设计是只支持合并，不支持拆分的，因为路径压缩和按秩合并这些优化，会破坏集合树形结构的可追溯性，使得拆分操作无法高效且正确地执行。你的拆分方案本质上是一种临时hack，仅在特定场景下能工作，存在效率和正确性隐患。

正确的拆分实现方案

如果业务场景必须支持拆分操作，有三种可行方向：

1. 放弃路径压缩，改用可追溯树形结构

移除find中的路径压缩逻辑，让每个元素的父节点始终指向直接上级，而非根节点。拆分时：

确认要拆分的子集c是原集合中的连通分支（通过图遍历验证）。
将c中所有元素的父节点改为newParent，调整setCount。
但这种方式会让find操作的时间复杂度退化为O(n)，失去DSU的高效性。

2. 使用支持动态连通性的替代数据结构

如果需要高效支持合并和拆分，推荐使用Link-Cut Tree（动态树）或者Euler Tour Tree（ETT），这些数据结构专门设计用于处理动态连通性问题，支持高效的合并、拆分和连通性查询操作。

3. 重建DSU（最直接的临时方案）

如果数据规模不大，或者拆分操作频率很低，最简单的方式是：

遍历所有节点，通过邻接表记录当前所有存在的边。
清空原DSU，重新添加所有节点，并根据当前边重新执行合并操作。
这种方式实现简单，但效率较低，适合小数据量场景。

针对当前代码的优化建议

如果坚持使用现有DSU的拆分方案，不需要全量执行find，只需要确保原集合中所有不在c里的元素，父节点最终指向oldParent：

先对oldParent所在集合的所有元素执行find（而非全局所有元素），确保所有元素的父节点都直接指向oldParent。
再修改c中元素的父节点为newParent，并增加setCount。
这样可以减少不必要的find操作，提升效率。

内容的提问来源于stack exchange，提问作者TripleCamera

如何正确实现不相交集合（Disjoint Set）的拆分操作？

遇到的问题 #

为什么全量执行find能修复bug？ #

不相交集合（DSU）的本质限制 #

正确的拆分实现方案 #