图切割与连通性查询场景下DSU频繁重建的优化方案咨询

算力阿峰

2026-7-4

动态图的边删除与连通性查询优化方案

问题背景

我有一项大学作业，需要实现图的切割功能：当收到cut指令时移除图中的一条边，收到ask指令时判断两个顶点是否存在路径连通。我使用*Union Find（DSU）*实现该功能，每当有修改后进行查询时，都需要重建DSU。目前结果正确，但我对每次都要重建DSU的效率不满意。是否有更高效的实现方式？我曾考虑能否直接从DSU中移除边，但尚未找到可行方案，希望能得到相关提示。

现有实现代码

#include <bits/stdc++.h>
using namespace std;

struct Edge{
    int startIndex, endIndex;
};

struct UndirectedGraph{
    int numberOfVertices, numberOfEdges;
    vector<Edge> edges; 
};

struct subset{
    int parent;
    int rank;
};

struct UndirectedGraph createGraph(int numberOfVertices, int numberOfEdges){
    UndirectedGraph undirectedGraph;    
    undirectedGraph.numberOfVertices = numberOfVertices;
    undirectedGraph.numberOfEdges = numberOfEdges;
    undirectedGraph.edges = vector<Edge>(numberOfEdges);
    return undirectedGraph;
}

int find(subset subsets[], int i){
    if (subsets[i].parent != i)
    {
        subsets[i].parent = find(subsets, subsets[i].parent); 
    }
    return subsets[i].parent;
}

void unionSubsets(subset subsets[], int index1, int index2){
    int newIndex1 = find(subsets, index1); 
    int newIndex2 = find(subsets, index2); 
    // Hängt den Teilbaum mit dem niedrigeren Rang unter die Wurzel des Baums mit dem höheren Rang
    if (subsets[newIndex1].rank < subsets[newIndex2].rank)
        subsets[newIndex1].parent = newIndex2;
    else if (subsets[newIndex1].rank > subsets[newIndex2].rank)
        subsets[newIndex2].parent = newIndex1;
    else{ // Wenn die Teilbäume denselben Rang haben, wird der Rang des einen Baums erhöht und der andere Baum unter die Wurzel des anderen Baums gehängt
        subsets[newIndex2].parent = newIndex1;
        subsets[newIndex1].rank++;
    }
}


subset* build(struct UndirectedGraph graph){
    vector<Edge> edges = graph.edges; 
    subset* subsets = new subset[graph.numberOfVertices]; 
    for (int i = 0; i < graph.numberOfVertices; i++){
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }
    for (int i = 0; i < graph.numberOfEdges; i++){
        Edge nextEdge = edges[i]; 
        int index1 = find(subsets, nextEdge.startIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.startIndex
        int index2 = find(subsets, nextEdge.endIndex); // Index der Wurzel der Teilmenge mit dem Index nextEdge.endIndex
        unionSubsets(subsets, index1, index2);
    }
    return subsets;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    struct UndirectedGraph graph = createGraph(n,m);
    vector<Edge>* edges = &graph.edges;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        (*edges)[i].startIndex = u-1;
        (*edges)[i].endIndex = v-1;
    }
    int cuted = 0;
    subset* sub = build(graph);
    for (int i = 0; i < k; ++i) {
        string query;   
        int u, v;
        cin >> query >> u >> v;
        if (query == "cut") {            
            auto it = find_if(edges->begin(), edges->end(), [u, v](const Edge& edge) {
                return (edge.startIndex == u - 1 && edge.endIndex == v - 1) ||
                       (edge.startIndex == v - 1 && edge.endIndex == u - 1);
            });
            (*edges).erase(it);
            cuted = 1;
            graph.numberOfEdges -=1;
        } else if (query == "ask") {
            if(cuted){
                sub = build(graph);
                cuted = 0;
            }
            if (find(sub,u-1) == find(sub,v-1))
                cout << "YES" << endl;
            else{
                cout << "NO" << endl;
            }
        }   
    }
    return 0;
}

优化方案

普通的*Union-Find（DSU）*只支持高效的合并操作，不支持拆分操作（也就是删除边对应的连通关系），所以直接在DSU上删边行不通。针对这种带边删除的动态连通性问题，有两种主流优化思路：

1. 离线处理：时间倒流法

如果所有的查询（包括cut和ask）可以提前全部读取，优先用时间倒流的思路，实现简单且效率极高：

先记录所有操作，标记出所有最终未被cut的边。
从最终状态开始，把cut操作反向转为添加边的操作，ask操作按原顺序处理。
这样就可以用普通DSU处理，因为添加边是DSU擅长的操作，每次ask直接查询连通性即可，无需重建DSU。

具体步骤：

收集所有操作，给每条初始边标记是否会被删除。
初始化DSU，只加入最终保留的边。
从最后一个操作往前遍历：
- 遇到cut操作，就把对应的边加回DSU（执行union）。
- 遇到ask操作，记录当前连通性结果，最后将结果反转输出。

该方法时间复杂度为$O((n+m+k)\alpha(n))$，$\alpha$是阿克曼函数的反函数，效率接近线性。

2. 在线处理：使用动态连通性数据结构

如果必须在线处理（无法提前获取所有操作），可以使用Link-Cut Tree（维护动态树连通性）或专门的动态连通性数据结构，这类结构支持：

link(u, v)：添加边u-v。
cut(u, v)：删除边u-v。
connected(u, v)：判断u和v是否连通。

不过这类数据结构实现复杂度较高，大学作业场景下，若允许离线处理，优先选时间倒流法。

3. 当前代码的轻量优化

如果必须在线且不想实现复杂结构，可以优化现有逻辑：

不要每次cut后标记重建，而是缓存当前DSU，累积多次cut后再一次性重建。
用哈希表记录被删除的边，重建DSU时跳过这些边，避免频繁的vector erase操作（erase是$O(m)$时间）。比如用unordered_set存储被删边的哈希值，build时遍历初始边，跳过标记删除的边。

这能减少部分不必要的开销，但本质还是重建DSU，属于临时优化方案。

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