Number of Operations to Make Network Connected

class DisjointSet {
private:
    vector<int> leader, depth;
    
public:
    DisjointSet(int count) {
        leader.resize(count);
        depth.resize(count, 0);
        for (int i = 0; i < count; i++) {
            leader[i] = i;
        }
    }
    int find(int p) {
        if (leader[p] != p) leader[p] = find(leader[p]);
        return leader[p];
    }
    void unite(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (depth[rootA] < depth[rootB]) {
            leader[rootA] = rootB;
        } else if (depth[rootA] > depth[rootB]) {
            leader[rootB] = rootA;
        } else {
            leader[rootB] = rootA;
            depth[rootA]++;
        }
    }
};
    
class NetworkSolution {
public:
    int connectComponents(int nodes, vector<vector<int>>& edges) {
        if (edges.size() < nodes - 1) {
            return -1;
        }
    
        DisjointSet dsu(nodes);
        int connectedComponents = nodes;
        for (auto& edge : edges) {
            if (dsu.find(edge[0]) != dsu.find(edge[1])) {
                connectedComponents--;
                dsu.unite(edge[0], edge[1]);
            }
        }
    
        return connectedComponents - 1;
    }
};

The provided C++ code aims to determine the number of operations required to make a network fully connected using a Disjoint Set Union (DSU) data structure, optimized for union by rank and path compression. Here’s a breakdown of how the code achieves this:

• DisjointSet Class Implementation:

  • Initializes with two vectors, leader and depth, where leader[i] holds the parent of element i and depth[i] holds the depth of the tree rooted at i.
  • The find function recursively finds the root leader of an element p and employs path compression to flatten the structure for future accesses.
  • The unite function merges two subsets. Uses union by rank, where the deeper tree remains the root, preventing the tree from becoming skewed.

• NetworkSolution Class Implementation:

  • Method connectComponents takes the number of nodes and a list of edges, returning the number of required operations.
  • It returns -1 directly if the number of edges is less than nodes minus one, since at least n-1 edges are needed to connect n nodes.
  • It counts the connected components. Every time it unites two separate components, it reduces the count.
  • Ultimately, it adjusts the count of components (subtracts one) to determine the required number of additional connections (operations).

The DSU data structure enables efficient operations for determining whether two nodes are in the same component and for uniting two components, thus enabling the calculation of the minimum number of connections needed to make the entire network connected efficiently.

class DisjointSet {
    int[] leader;
    int[] size;
    
    public DisjointSet(int capacity) {
        leader = new int[capacity];
        for (int i = 0; i < capacity; i++)
            leader[i] = i;
        size = new int[capacity];
    }
    
    public int root(int x) {
        if (leader[x] != x)
            leader[x] = root(leader[x]);
        return leader[x];
    }
    
    public void connect(int x, int y) {
        int rootX = root(x), rootY = root(y);
        if (rootX == rootY) {
            return;
        } else if (size[rootX] < size[rootY]) {
            leader[rootX] = rootY;
        } else if (size[rootX] > size[rootY]) {
            leader[rootY] = rootX;
        } else {
            leader[rootY] = rootX;
            size[rootX]++;
        }
    }
}
    
class Solution {
    public int makeConnected(int n, int[][] connections) {
        if(connections.length < n-1) {
            return -1;
        }
    
       DisjointSet dsu = new DisjointSet(n);
        int numberOfConnectedComponents = n;
        for (int[] connection : connections) {
            if (dsu.root(connection[0]) != dsu.root(connection[1])) {
                numberOfConnectedComponents--;
                dsu.connect(connection[0], connection[1]);
            }
        }
    
        return numberOfConnectedComponents - 1;
    }
}

This Java program aims to find the minimum number of operations required to make all computers in a network connected using a given number of connections. The core challenge is to determine if enough connections exist to connect all computers and, if sufficient, how many additional connections are needed.

The implementation employs a Disjoint Set Union (DSU) or Union-Find data structure, particularly useful for solving network connectivity problems efficiently:

• DisjointSet Class: Handles the union-find operations.

  • leader: Tracks the leader or representative of each set.
  • size: Assists in optimizing union operations by size.
  • Operations include finding the root of a set (root method) and connecting two sets (connect method).

• Solution Class:

  • makeConnected Function: This is where the main logic is implemented.
    1. First, check if the number of connections is less than n-1. If yes, return -1 as it's impossible to connect all computers.
    2. Initialize the DisjointSet with n computers.
    3. Iterate through the given connections. If the root of the two connected computers differs, decrease the number of connected components and connect them in the DisjointSet.
    4. Finally, return the number of required additional connections as numberOfConnectedComponents - 1.

By the conclusion of this flowchart, the function makeConnected determines whether it is possible to connect all components and, if so, returns the minimum number of additional connections needed. This scenario assumes that direct connections are always bidirectional and that computers form a zero-indexed list.