Problem Statement

Given a graph with n vertices and m edges. The graph is represented by an array Edges, where Edge[i] = [a, b] indicates an edge between vertices a and b. One edge can be removed from anywhere and added between any two vertices in one operation. Find the minimum number of operations that will be required to make the graph connected. If it is not possible to make the graph connected, return -1.

Examples

Example 1:

Input: n = 4,
       Edge = [
               [0,1],
               [0, 2],
               [1, 2]
              ]
Output: 1

Explanation: We need a minimum of 1 operation to make the two components connected. We can remove the edge (1, 2), and add the edge between node 2 and node 3 like the following.

Example 2:

Input: n = 9,
       Edge = [
               [0, 1],
               [0, 2],
               [0, 3],
               [1, 2],
               [2, 3],
               [4, 5],
               [5, 6],
               [7, 8]
              ]
Output: 2

Explanation: We need a minimum of 2 operations to make the two components connected. We can remove the edge (0, 2) and add the edge between node 3 and node 4 and we can remove the edge (0, 3) and add it between nodes 6 and 8 like the following.

Different Approaches

1️⃣ Disjoint Set Data Structure

Intuition:

The problem involves removing an edge and adding it between two other nodes, indicating that the graph is updating continuously. This gives the idea of using the Disjoint Set Data Structure.

Now, to make the graph connected, all the different components of the graphs must be connected to each other (directly or indirectly). The minimum number of edges required to connect all the components is always one lesser than the number of components. Hence, the problem boils down to finding the number of components in the given graph. Once found, the minimum number of edges to connect the graph can be found. If the number of edges present in the graph is less than that required to connect the graph, it is impossible to connect the graph and thus -1 can be returned.

Approach:

1. Check if it is possible to connect the graph or not. If found not possible, return -1.
2. Initialize a Disjoint Set to manage connected components.
3. Process each edge to unify connected vertices.
4. Count the number of connected components by identifying unique parents.
5. The required operations are the number of connected components minus one.

Code:

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

class DisjointSet {
public:
    /* To store the ranks, parents and 
    sizes of different set of vertices */
    vector<int> rank, parent, size;

    // Constructor
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
    
    // Function to find ultimate parent
    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }
    
    // Function to implement union by rank
    void unionByRank(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
    
    // Function to implement union by size
    void unionBySize(int u, int v) {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v) return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};

// Solution class
class Solution{
public:

    /* Function to get the number of 
    operations to make network connected */
    int solve(int n, vector<vector<int>> &Edge){
        
        // Get the number of edges
        int size = Edge.size();
        
        /* Return -1 if connecting all 
        vertices is not possible */
        if(size < n-1) return -1;
        
        // Disjoint Set data structure
        DisjointSet ds(n);
        
        // Add all the edges in the set
        for(int i=0; i<size; i++) {
            ds.unionByRank(Edge[i][0], Edge[i][1]);
        }
        
        // To store count of required edges
        int count = 0;
        
        // Finding the number of components
        for(int i=0; i<n; i++) {
            if(ds.parent[i] == i) count++;
        }
        
        // Return the result
        return count-1;
    }
};


int main() {
    int n = 4;
    vector<vector<int>> Edge = {
        {0, 1}, 
        {0, 2}, 
        {1, 2}
    };

    // Creating instance of Solution class
    Solution sol;
    
    /* Function call to get the number of 
    operations to make network connected */
    int ans = sol.solve(n, Edge);
    
    cout << "The number of operations to make network connected is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(N+M) (where N and M represent the number of vertices and edges in the graph)
  • Adding all M edges to the disjoint set takes O(M) time, and finding the number of components in the graph by finding unique ultimate parent node takes O(N) time.
• Space Complexity:O(N)
  • The Disjoint Set data structure uses the parent and size/rank arrays of O(N) size each to perform the Union operation and to find the Ultimate parent.