剪切图表或 DSU

Question

我收到了一份大学作业，必须剪一张图表。每当我被切割时，我应该从图中删除边，当我被问到时，我应该检查两个顶点是否连接。

我与 Union find 合作，每当有人询问我并且某些内容发生变化时，我都会重建。到目前为止结果是正确的，但我对每次都必须重建我的 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;
}

Answer 1

我建议你使用邻接矩阵。如果顶点 u 和 v 连接，则矩阵将 1 存储在 u 行 v 列的单元格中

要检查两个顶点是否连接，您只需查找单元即可。

要删除边缘，只需将相应单元格的值设置为 0。

其他一切保持不变 - 无需重建。

这就是您所需要的：

#include <string>
#include <iostream>
#include <vector>
#include <stdexcept>


int main()
{
    std::vector<std::vector<bool>> M(
        1000,
        std::vector<bool>(1000, false));

    std::cout <<  "Enter vertices connected by edges, '-1 -1' to end\n";
    while (std::cin.good())
    {
        int u, v;
        std::cin >> u >> v;
        if( u < 0  )
            break;
        if( u > 999 || v > 999)
            throw std::runtime_error("max index exceeded");
        M[u][v] = true;
    }

    std::cout << "enter query,'end' to end\n";
    while (std::cin.good())
    {
        std::string query;
        int u, v;
        std::cin >> query >> u >> v;
        if (query == "cut")

            M[u][v] = false;

        else if (query == "ask")
        {
            if (M[u][v])
                std::cout << "YES\n";
            else
                std::cout << "NO\n";

        } else if (query == "end")
            break;
    }
    return 0;
}