✅ 🔥 Connected Networks | Java | Union_Find 🔥✅
Hi,\n\nThe basic understanding to connect n nodes requires a minimum of n-1 edges. In case of multiple groups of nodes we might need more nodes as they may be i
Hi,\n\nThe basic understanding to connect n nodes requires a minimum of n-1 edges. In case of multiple groups of nodes we might need more nodes as they may be in tree like data structure.\n\nUsing the above approach we have to see whether n-1 edges are available. And to get the multiple group of nodes we use union find.\n\n1. Initially the parent for all the nodes will the node itself\n2. If two nodes are connected then we use Union method to join the nodes with parent of second node as first node\n3. Find the parent of the node by looking into the parent array until you reach the node where the parent of the node is the node itself\n4. Finally count the number of groups and not connected nodes by finding the number of parent nodes with unique values.\n5. Return the count-1.\n\n```\n    public int makeConnected(int n, int[][] roads) {\n    \tif(roads.length<n-1)\n    \t\treturn -1;\n    \tint parent[] =  new int[n];\n    \tfor(int i=0; i<n; i++){\n    \t\tparent[i]=i;\n    \t}\n    \tfor(int[] i: roads){\n    \t\tunion(i[0], i[1], parent);\n    \t}\n    \tint res=0;\n    \tfor(int i=0; i<n; i++){\n    \t\tif(parent[i]==i)\n    \t\t\tres++;\n    \t}\n    \treturn res-1;\n    }\n\t\n    private void union(int i, int j, int[] parent) {\n\t\tif(find(i, parent)!=find(j, parent)){\n\t\t\tparent[parent[j]] = parent[i];\n\t\t}\n\t\t\n\t}\n\n\tprivate int find(int i, int[] parent) {\n\t\tif(parent[i]!=i)\n\t\t\tparent[i] = find(parent[i], parent);\n\t\treturn parent[i];\n\t}
['Union Find', 'Java']