JAVA Simple Solution | Union Find | Disjoint set | with comments
(Don\'t worry the code seems lengthy but easy to understand)\nSteps to solve the problem \n\n1. Find the total number of loops/cycles in the given graph.\n2. Fi
**(*Don\'t worry the code seems lengthy but easy to understand*)**\n**Steps to solve the problem** \n\n**1.** Find the total number of loops/cycles in the given graph.\n**2.** Find total number of isolated components (computers).\n**3.** If we have a cycle means we have an extra connection(wire) which we can use to connect the unconnected components.\n**4.** So we can return total number of unconnected components(computers) as an answer because that much amount of wires will be required optimally to connect them with the graph,only if we have sufficiant extra wires, i.e cycles >= unconnected components.\n\nTo find the total cycles we are using Union Find method, where we are maintaining a parent array to store ultimate parents of every node/component.\nWe can determine whether 2 nodes are in the same connected component or not in the graph.\n\n```\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        int[] parent = new int[n];  // Array to find the ultimate parent in union find method.\n        \n        for(int i=0;i<n;i++) parent[i] = i;  // At first all the elements are not connected we combine them gradually according to our given graph of connections.\n        \n        int cycles = 0;  // Variable to store total number of cycles/loops.\n        \n        int unconnected_computers = 0;  // variable to store total unconnected components.\n        \n        for(int[] link : connections) {\n            \n            int from = link[0];\n            int to = link[1];\n            \n            if(find_parent(from, parent) == find_parent(to, parent)) cycles++;  // if parent of one node is equal to parent of other node which implies that both nodes are connected previously and forms a cycle with this union.\n            \n            union(from, to, parent);\n            \n        }\n        \n        // loop to count total number of unconnected components.\n        for(int i=0;i<n;i++) {\n            if(parent[i] == i) unconnected_computers++;\n        }\n    \n        // Number of cycles represents Number of extra connections, which we can use to connect the unconnected computers.\n        if(cycles >= unconnected_computers-1) return unconnected_computers-1;\n        return -1;\n    }\n    \n    // Method to find parent of every node.\n    public int find_parent(int node, int[] parent) {\n        if(parent[node] == node) return node;\n        return find_parent(parent[node], parent);\n    }\n    \n    // Method to create the union of two sets.\n    public void union(int from, int to, int[] parent) {\n        from = find_parent(from, parent);\n        to = find_parent(to, parent);\n        \n        parent[to] = from;\n    }\n}\n```
['Union Find', 'Java']