DAY 47 - Number of Operations to make network connected

Hey everyone! Welcome back to another day of problem-solving. It's day 47, and I'm still going strong on my quest for consistency. Today, We will be solving a problem using Disjoint Data Sets.
A prerequisite to solving this would be knowing about disjoint data sets.
I suggest reading the previous article in this series.

Question Number of Operations to make network connected

There are n computers numbered from 0 to n - 1 connected by ethernet cables connections forming a network where connections[i] = [ai, bi] represents a connection between computers ai and bi. Any computer can reach any other computer directly or indirectly through the network.

You are given an initial computer network connections. You can extract certain cables between two directly connected computers, and place them between any pair of disconnected computers to make them directly connected.

Return the minimum number of times you need to do this in order to make all the computers connected. If it is not possible, return -1.

Example 1:

Input: n = 4, connections = [[0,1],[0,2],[1,2]]
Output: 1
Explanation: Remove cable between computer 1 and 2 and place between computers 1 and 3.

Intuition:

Let's break down the question.
We are given n computers and We need to connect each other to everyone either indirectly or directly.
The thing is we have to do it in minimum number of operations and we can only do it so by removing a connection between two computers.

So things we must keep in mind are:

• Connections we can remove without disrupting an existing connection so that we don't lose that.
• Maximum connections that we will need would be n-1 computers as to connect n computers we need n-1 connections.
• Example: n = 5. 1<->2<->3<->4<->5
• So now we just use the disjoint set which contains the parent to solve this.
• Two computers having same two super parents are connected.
• If we find an edge that will connect two computers who are already some way connected to the same super parent we can count that as an extra edge.
• If our number of extra edges >= no of different parents-1
• We can return our no of different parents-1 else we can return -1.

Algorithm:

• Create a DisjointSet object ds with n nodes.
• Initialize an integer extras to keep track of the number of extra connections (edges) that create cycles.
• For each connection (edge) represented as a pair (u, v) in connections:
• Check if nodes u and v have the same ultimate parent (in the same component) using ds.findUPar(u) and ds.findUPar(v).
• If they have the same parent, it means adding this edge will create a cycle, so increment extras.
• Otherwise, perform a union of nodes u and v using ds.unionByRank(u, v) and ds.unionByRank(v, u).
• Initialize an integer diffParents to count the number of different parent nodes in the disjoint set.
• Traverse all nodes in the disjoint set, and if a node's parent is itself, increment diffParents.
• If extras is greater than or equal to diffParents - 1, it means there are enough extra connections to connect all nodes in a single component, so return diffParents - 1.
• Otherwise, return -1 as it is not possible to connect all nodes in a single component.

Code:

class DisjointSet {
    public:
    vector<int> rank, parent;
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
    }

    int findUPar(int node) {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }

    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]++;
        }
    }
};

class Solution {
public:
    int makeConnected(int n, vector<vector<int>>& connections) {
        // n is no of edges
        //connections contain edge sets
        int extras;
        DisjointSet ds(n);
        for(auto it : connections){
            int u = it[0];
            int v = it[1];
            if(ds.findUPar(u) == ds.findUPar(v)){
                extras++;   
            }
            else{
            ds.unionByRank(v,u);
            ds.unionByRank(u,v);
            }
        }

        int diffParents = 0;
        for(int i = 0; i < n; i++){
            if(ds.parent[i] == i){
                diffParents++;
            }
        }
        cout << diffParents << endl;
        cout << extras;
        if(extras >= diffParents-1 ){
            return diffParents-1;
        }
        return -1;
    }
};

Complexity Analysis:

Time: O((E+N)*4alpha)
Space: O(N)

Thanks for reading. Feedback is highly appreciated!.