JAVA DISJOINTSET SOLUTION✅✅
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n Describe your approach to solving the problem. \n\n# Complexity\n- Time 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> O(m * log(n))\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->O(n)\n![Screenshot_20230205_171246.png](https://assets.leetcode.com/users/images/2afc34cc-04fa-4568-80e2-60c92cf26a80_1693710877.7233145.png)\n\n\n# Code\n```\nclass DisjointSet {\n    List<Integer> size = new ArrayList<>();\n    List<Integer> parent = new ArrayList<>();\n    \n    public DisjointSet(int n) {\n        // Initialize the parent and size lists for each node.\n        for (int i = 0; i <= n; i++) {\n            parent.add(i);  // Each node is initially its own parent.\n            size.add(1);    // Initially, each set has a size of 1.\n        }\n    }\n    \n    public int findUPar(int node) {\n        if (node == parent.get(node)) {\n            return node;  // If the node is its own parent, it\'s the representative of its set.\n        }\n        // Recursively find the ultimate parent and update the parent list for path compression.\n        int ulp = findUPar(parent.get(node));\n        parent.set(node, ulp); // Path compression: update the parent to the ultimate parent.\n        return parent.get(node);\n    }\n    \n    public void unionBySize(int u, int v) {\n        int ulp_u = findUPar(u);  // Find ultimate parent of u.\n        int ulp_v = findUPar(v);  // Find ultimate parent of v.\n        \n        if (ulp_u == ulp_v) return;  // If they share the same parent, they are in the same set.\n        \n        if (size.get(ulp_u) < size.get(ulp_v)) {\n            // Attach the smaller set to the larger set and update the size.\n            parent.set(ulp_u, ulp_v);\n            size.set(ulp_v, size.get(ulp_v) + size.get(ulp_u));\n        } else {\n            parent.set(ulp_v, ulp_u);\n            size.set(ulp_u, size.get(ulp_u) + size.get(ulp_v));\n        }\n    }\n}\n\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        \n        DisjointSet ds = new DisjointSet(n);\n\n        int m = connections.length;\n        int extraEdges = 0;\n\n        // Check each connection and determine if it creates an extra edge or connects existing components.\n        for (int i = 0; i < m; i++) {\n            int u = connections[i][0];\n            int v = connections[i][1];\n\n            if (ds.findUPar(u) == ds.findUPar(v)) {\n                extraEdges++; // The connection creates an extra edge within the same component.\n            } else {\n                ds.unionBySize(u, v); // Union the two nodes to connect their components.\n            }\n        }\n\n        int connectedComponents = 0;\n\n        // Count the number of connected components in the disjoint set.\n        for (int i = 0; i < n; i++) {\n            if (ds.findUPar(i) == i) {\n                connectedComponents++;\n            }\n        }\n\n        int requiredEdges = connectedComponents - 1;\n\n        if (extraEdges >= requiredEdges) {\n            return requiredEdges; // There are enough extra edges to connect all components.\n        }\n        return -1; // Not enough extra edges to connect all components.\n    }\n}\n\n```
['Union Find', 'Graph', 'Java']