Class Solution

NumberOfOperationsToMakeNetworkConnected.java:1–20

class Solution {
    public int makeConnected(int n, int[][] connections) {
        //atleast n-1 edges are required to connect all nodes into a single component
        if(connections.length < n-1){ 
            return -1;
        }
        int wires=0;
        DisjointSet dsu = new DisjointSet(n);
        for(int connection[] : connections){
            int u = connection[0];
            int v = connection[1];
            if(dsu.unionBySize(u,v)){
                wires++;
            }
        }
        //for connecting n nodes, we require a minimum of n-1 edges
        // so minimum wires requires = (n-1) - (wires-used) 
        return n-1-wires;
    }
}

public class DisjointSet {
    int parent[];