From 75% to 100% || Union Find || With Images || Java, c++  🚀
Intuition\nFeels like grouping of networks right?\nHow can we group some objects based on connections?\nWell, the answer is to use the union find method. All th
# Intuition\nFeels like grouping of networks right?\nHow can we group some objects based on connections?\nWell, the answer is to use the union find method. All the nodes that are connected, will be part of a group.\n\nFor example 1:\n```\nInput: n = 4, connections = [[0,1],[0,2],[1,2]]\n\n```\n\n![image.png](https://assets.leetcode.com/users/images/f446870e-e6f0-4408-a263-2884ace49ba9_1679561017.4923828.png)\n\n\nFor example 3:\n```\nInput: n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]\n\n```\n\n![image.png](https://assets.leetcode.com/users/images/26d9d9c3-1783-4529-8d38-81e7593e9187_1679561314.1289692.png)\n\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nUnion Find with ranks.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(N+E)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(N)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# 75% Efficient:\n\n``` Java []\nclass Solution {\n    int[] parent;\n    int[] rank;\n    int find(int x){\n        while(parent[x]!=x){\n            x = parent[parent[x]];\n        }\n        return x;\n    }\n    void makeUnion(int x, int y){\n        int parX = find(x);\n        int parY = find(y);\n        if(parX == parY){\n            return;\n        }\n        else if(rank[parX]<rank[parY]){\n            parent[parX] = parY;\n        }\n        else if(rank[parX]>rank[parY]){\n            parent[parY] = parX;\n        }\n        else{\n            parent[parY] = parX;\n            rank[parX]++;\n        }\n    }\n    public int makeConnected(int n, int[][] connections) {\n        int edges = connections.length;\n        if(edges<n-1){\n            return -1;\n        }\n        parent = new int[n];\n        rank = new int[n];\n        for(int i=0; i<n; i++){\n            parent[i] = i;\n        }\n        for(int[] con : connections){\n            makeUnion(con[0], con[1]);\n        }\n        Set<Integer> set = new HashSet<>();\n        for(int i=0; i<n; i++){\n            int par = find(i);\n            set.add(par);\n        }\n        int unions = set.size();\n        return unions-1;\n    }\n}\n\n```\n``` C++ []\nclass Solution {\npublic:\n    int find(int x, int parent[]){\n        while(parent[x]!=x){\n            x = parent[parent[x]];\n        }\n        return x;\n    }\n\n    void makeUnion(int x, int y, int parent[], int rank[]){\n        int parX = find(x, parent);\n        int parY = find(y, parent);\n        if(parX == parY){\n            return;\n        }\n        else if(rank[parX]<rank[parY]){\n            parent[parX] = parY;\n        }\n        else if(rank[parX]>rank[parY]){\n            parent[parY] = parX;\n        }\n        else{\n            parent[parY] = parX;\n            rank[parX]++;\n        }\n    }\n\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        int edges = connections.size();\n        if(edges<n-1){\n            return -1;\n        }\n        int parent[n];\n        int rank[n];\n        for(int i=0; i<n; i++){\n            parent[i] = i;\n        }\n        for(auto con : connections){\n            makeUnion(con[0], con[1], parent, rank);\n        }\n        set<int> groups;\n        for(int i=0; i<n; i++){\n            int par = find(i, parent);\n            groups.insert(par);\n        }\n        int unions = groups.size();\n        return unions-1;\n    }\n};\n```\n\n# 100% Efficient:\n\n\n``` Java []\nclass Solution {\n    int[] parent;\n    int[] rank;\n    int find(int x){\n        while(parent[x]!=x){\n            x = parent[parent[x]];\n        }\n        return x;\n    }\n    int makeUnion(int x, int y){\n        int parX = find(x);\n        int parY = find(y);\n        if(parX == parY){\n            return 0;\n        }\n        else if(rank[parX]<rank[parY]){\n            parent[parX] = parY;\n        }\n        else if(rank[parX]>rank[parY]){\n            parent[parY] = parX;\n        }\n        else{\n            parent[parY] = parX;\n            rank[parX]++;\n        }\n        return 1;\n    }\n    public int makeConnected(int n, int[][] connections) {\n        int edges = connections.length;\n        if(edges<n-1){\n            return -1;\n        }\n        parent = new int[n];\n        rank = new int[n];\n        for(int i=0; i<n; i++){\n            parent[i] = i;\n        }\n        int components = n;\n        for(int[] con : connections){\n            components -= makeUnion(con[0], con[1]);\n        }\n        return components-1;\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    int find(int x, int parent[]){\n        while(parent[x]!=x){\n            x = parent[parent[x]];\n        }\n        return x;\n    }\n\n    int makeUnion(int x, int y, int parent[], int rank[]){\n        int parX = find(x, parent);\n        int parY = find(y, parent);\n        if(parX == parY){\n            return 0;\n        }\n        else if(rank[parX]<rank[parY]){\n            parent[parX] = parY;\n        }\n        else if(rank[parX]>rank[parY]){\n            parent[parY] = parX;\n        }\n        else{\n            parent[parY] = parX;\n            rank[parX]++;\n        }\n        return 1;\n    }\n\n    int makeConnected(int n, vector<vector<int>>& connections) {\n        int edges = connections.size();\n        if(edges<n-1){\n            return -1;\n        }\n        int parent[n];\n        int rank[n];\n        for(int i=0; i<n; i++){\n            parent[i] = i;\n        }\n        int components = n;\n        for(auto con : connections){\n            components -= makeUnion(con[0], con[1], parent, rank);\n        }\n        return components-1;\n    }\n};\n\n```\n\n![image.png](https://assets.leetcode.com/users/images/05ec548b-8f31-4b4d-88c1-50cfa8ad7d7e_1679561909.9536836.png)\n\n![image.png](https://assets.leetcode.com/users/images/1788262d-a9a0-418a-b0b4-bb5b97a59ca0_1679561923.9796534.png)\n
['Union Find', 'C++', 'Java']