Cut a Graph or DSU

Question

I had an assignment from university where I had to cut a graph. Whenever I get cut I should remove the edge from the graph and when I get ask I should check if the two vertices are with a path connected.

I worked with Union find and whenever I was asked and something was changed I rebuild. The result is correct so far, but I am not satisfied with the fact that my DSU has to be rebuilt every time. Is there a way I can do this more efficiently? I have thought about whether there might be a way to remove an edge directly from the DSU but have not yet found a satisfactory solution. I would be grateful for a hint.

#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

I suggest you use an adjacency matrix. If vertices u and v are connected, the matrix stores a 1 in the cell at row u and column v

To check if two vertices are connected you do a breadth first search.

To remove an edge you simply set the value of the corresponding cell to 0.

Everything else remains untouched - no rebuilding required.

This is all you need:

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

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

std::vector<int>
adjacent(int v)
{
    std::vector<int> ret;
    for (int u = 0; u < 1000; u++)
    {
        if (M[v][u])
            ret.push_back(u);
    }
    return ret;
}

bool isPath(int start, int end)
{

    // queue of visited vertices with unsearched children
    std::queue<int> Q;

    // track nodes that have been visited
    // prevent getting caught going around and around a cycle
    std::vector<bool> visited(M.size(), false);

    // start at start
    int v = start;
    Q.push(v);
    visited[v] = true;

    // loop while the queue is not empty
    while (!Q.empty())
    {
        // get current vertex from front of queue
        v = Q.front();
        Q.pop();

        // loop over vertices reachable from current vertex
        for (int u : adjacent(v))
        {
            if (u == end)
            {
                // reached the destination, no need to search further
                return true;
            }
            if (!visited[u])
            {
                // visit to a new node
                // because this is BFS, the first visit will be from
                // the previous node on the shortest path

                // add to queue, and mark visited
                Q.push(u);
                visited[u] = true;
            }
        }
    }
    return false;
}

int main()
{

    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 (u < 0 || v < 0)
            throw std::runtime_error("bad index");
        if (u > 999 || v > 999)
            throw std::runtime_error("max index exceeded");
        if (query == "cut")

            M[u][v] = false;

        else if (query == "ask")
        {
            if (isPath(u,v))
                std::cout << "YES\n";
            else
                std::cout << "NO\n";
        }
        else if (query == "end")
            break;
    }
    return 0;
}

Output from test run

Enter vertices connected by edges, '-1 -1' to end
1 2
2 3
-1 -1
enter query,'end' to end
ask 1 3
YES
ask 3 1
NO