Union Find concept and multiple solutions - Java
Hello Guys, \n\nList of all Union Find related problems:\n1. https://leetcode.com/problems/redundant-connection/\n2. https://leetcode.com/problems/redundant-con
Hello Guys, \n\nList of all Union Find related problems:\n1. https://leetcode.com/problems/redundant-connection/\n2. https://leetcode.com/problems/redundant-connection-ii/\n3. https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/\n4. https://leetcode.com/problems/number-of-operations-to-make-network-connected/\n5. https://leetcode.com/problems/number-of-provinces/\n6. https://leetcode.com/problems/accounts-merge/description/\n\nThere is a similar code for the simple concept. I hope this Helps:\n\n**1. 684. Redundant Connection**\n```\n// Union Find\nclass Solution {\n    \n    int[] parent;\n    public int[] findRedundantConnection(int[][] edges) {\n        parent = new int[edges.length+1];\n        \n        for(int i=0; i<parent.length; i++) {\n            parent[i] = i;\n        }\n        \n        for(int[] edge : edges) {\n            if(find(edge[0]) == find(edge[1])) {\n                return edge;\n            }\n            \n            union(edge[0], edge[1]);\n        }\n        \n        return new int[]{-1,-1};\n    }\n    \n    \n    // Find Operation\n    private int find(int node) {\n        while(parent[node] != node) {\n            node = parent[node];\n        }\n        \n        return node;\n    }\n    \n    //Find Union Operation\n    private void union(int i, int j) {\n        int iRoot = find(i);\n        int jRoot = find(j);\n        \n        if(iRoot != jRoot) {\n            parent[jRoot] = iRoot;\n        }\n    }\n}\n```\n\n**2. 685. Redundant Connection II**\n\n```\n/*\nTo  detect a cycle in Directed graph, there are two possible cases.\n\nCase 1: There is a cycle but every node has a single parent\nCase 2: These is no cycle but a single node has two or more parents\n\n1)    5<-----1----->2                 2)            5<-----1----->2\n             ^      |                                      |      | \n             |      |                                      |      |\n             |      V                                      V      V \n             4<-----3                                      4<-----3 \n*/\t\t\t \nclass Solution {\n    \n    int[] parent;\n    \n    public int[] findRedundantDirectedConnection(int[][] edges) {\n        parent = new int[edges.length+1];\n        \n        int[] ans1 = null;\n        int[] ans2 = null;\n        \n\t\t// checking that how many parents are possible for each node\n        for(int[] edge : edges) {\n            int u = edge[0];\n            int v = edge[1];\n            \n            if(parent[v] > 0) {\n                ans1 = new int[]{parent[v], v};\n                ans2 = edge;      // Last possible edge which is creating the cycle - need to return this of we have multiple answer\n            }\n            \n            parent[v] = u;\n        }\n        \n//         System.out.println(Arrays.toString(parent)+" "+Arrays.toString(ans1)+" "+Arrays.toString(ans2));\n        parent = new int[edges.length+1];\n        \n        for(int i=0; i<parent.length; i++) {\n            parent[i] = i;\n        }\n        \n        for(int[] edge: edges) {\n            \n            if(edge == ans2) continue;\n            \n            if(find(edge[0]) == find(edge[1])) {\n                return ans1 == null ? edge : ans1; \n            }\n            union(edge[0], edge[1]);\n        }\n        \n        return ans2;\n    }\n    \n    private int find(int node) {\n        while(parent[node] != node) {\n            node = parent[node];\n        }\n        \n        return node;\n    }\n    \n    private void union(int i, int j) {\n        int iRoot = find(i);\n        int jRoot = find(j);\n        \n        if(iRoot!=jRoot) {\n            parent[jRoot] = iRoot;\n        }\n        \n    }\n}\n```\n\n**3. 947. Most Stones Removed with Same Row or Column**\n```\nclass Solution {\n    public int removeStones(int[][] stones) {\n        int[] parent = new int[stones.length];\n        \n        Arrays.fill(parent, -1);\n        \n        for(int i=0; i<stones.length; i++) {\n            for(int j=i+1; j<stones.length; j++) {\n                int[] stone1 = stones[i];\n                int[] stone2 = stones[j];\n                \n                if(stone1[0] == stone2[0] || stone1[1] == stone2[1]) {\n                    union(i, j, parent);\n                }\n            }\n        }\n        \n        int component = 0;\n        for(int i=0; i<parent.length; i++) {\n            if(parent[i] == -1) {\n                component++;\n            }\n        }\n        \n        return stones.length-component;\n    }\n    \n    private int find(int node, int[] parent) {\n        while(parent[node]!=-1) {\n            node = parent[node];\n        }\n        \n        return node;\n    }\n    \n    private void union(int A, int B, int[] parent) {\n        int parentA = find(A, parent);\n        int parentB = find(B, parent);\n        \n        if(parentA != parentB) {\n            parent[parentB] = parentA;\n        }\n    }\n}\n```\n\n**4. 1319. Number of Operations to Make Network Connected**\n\n```\nclass Solution {\n    public int makeConnected(int n, int[][] connections) {\n        int[] parent = new int[n];\n        int extraCable = 0;\n        \n        Arrays.fill(parent, -1);\n        \n        for(int[] connection : connections) {\n            \n            if(find(connection[0], parent) == find(connection[1], parent)) {\n                extraCable++;\n            } else {\n                union(connection[0], connection[1], parent);\n            }\n        }\n        \n        int component = 0;\n        \n        for(int i=0; i<parent.length; i++) {\n           if( parent[i] == -1) {\n               component++;\n           }\n        }\n        \n        return extraCable >= (component-1) ? component-1 : -1;\n    }\n    \n    private int find(int node, int[] parent) {\n        while(parent[node] != -1) {\n            node = parent[node];\n        }\n        \n        return node;\n    }\n    \n    private void union(int a, int b, int[] parent) {\n        int parentA = find(a, parent);\n        int parentB = find(b, parent);\n        \n        if(parentA != parentB) {\n            parent[parentB] = parentA;\n        }\n    }\n}\n```\n\n**5. 547. Number of Provinces**\n\n```\n/*\n// Same as https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/\n\nclass Solution {\n    \n    int ans = 0;\n    public int findCircleNum(int[][] isConnected) {\n        \n        BFS(isConnected);\n        \n        return ans;\n    }\n    \n    private void BFS(int[][] isConnected) {\n        boolean[] visited = new boolean[isConnected.length];\n        \n        for(int i=0; i<isConnected.length; i++) {\n            if(visited[i] == false) {\n                ans++;\n                BFSHelper(isConnected, visited, i);\n            }\n        }\n    }\n    \n    private void BFSHelper(int[][] isConnected, boolean[] visited, int start) {\n        Queue<Integer> queue = new LinkedList<>();\n        queue.add(start);\n        visited[start] = true;\n        \n        while(!queue.isEmpty()) {\n            int node = queue.poll();\n            \n            for(int i=0; i<isConnected.length; i++) {\n                if(isConnected[node][i] == 1 && visited[i] != true) {\n                    queue.add(i);\n                    visited[i] = true;\n                }\n            }\n        }\n    }\n}\n*/\nclass Solution {\n    int[] parent;\n    public int findCircleNum(int[][] isConnected) {\n        parent = new int[isConnected.length];\n        int result = 0;\n        \n        Arrays.fill(parent, -1);\n        \n        for(int i=0; i<isConnected.length; i++) {\n            for(int j=0; j<isConnected[0].length; j++) {\n                if(isConnected[i][j] == 1) {\n                    union(i,j);\n                }\n            }\n        }\n        \n        for(int i=0; i<parent.length; i++) {\n            if(parent[i] == -1) {\n                result++;\n            }\n        }\n        \n        return result;\n    }\n    \n    private int find(int node) {\n        while(parent[node] != -1) {\n            node = parent[node];\n        }\n        \n        return node;\n    }\n    \n    private void union(int a, int b) {\n        int parentA = find(a);\n        int parentB = find(b);\n        \n        if(parentA != parentB) {\n            parent[parentB] = parentA;\n        }\n    }\n}\n```\n**6. 721. Accounts Merge**\n\n```\n/* This problem is simple concept as we have to use the union find concept here but code is slightly heavy.\n\nInput:\n[["John","J1@mail","J2@mail"],["John","J1@mail","J3@mail"],["Mary","m1@mail"],["John","J4@mail.com"]]\n\n\n        emailToIdx                          emailToName                         Parent\n\n        J1@mail     0                       J1@mail     John                0   1   2   3 (Indexes)\n        J2@mail     0                       J2@mail     John                0   0   2   3       \n        J3@mail     1                       J3@mail     John\n        m1@mail     2                       m1@mail     Mary\n        J4@mail     3                       J4@mail     John\n\n\n        Groups\n        0 ->    [J1@mail, J2@mail, J3@mail]\n        1 ->    []\n        2 ->    [m1@mail]\n        3 ->    [J4@mail]\n\n\n*/\n\nclass Solution {\n    int[] parent;\n    public List<List<String>> accountsMerge(List<List<String>> accounts) {\n        \n        Map<String, Integer> emailToIdx = new HashMap<>();\n\n        Map<String, String> emailToName = new HashMap<>();\n\n        parent = new int[accounts.size()];\n\n        for(int i=0; i<parent.length; i++) {\n            parent[i] = i;\n        }\n\n        int idx = 0;\n\n        for(List<String> account : accounts) {\n            String name = account.get(0);\n\n            for(int i=1; i<account.size(); i++) {\n                String curEmail = account.get(i);\n\n                if(!emailToIdx.containsKey(curEmail)) {\n                    emailToIdx.put(curEmail, idx);\n                    emailToName.put(curEmail, name);\n                }\n\n                // Union the first email with the current email\n                int firstEmailIdx = emailToIdx.get(account.get(1));\n                int curEmailIdx = emailToIdx.get(curEmail);\n\n                union(firstEmailIdx, curEmailIdx);\n            }\n            idx++;\n        }\n\n        // Grouping emails that belong to the same set\n        Map<Integer, TreeSet<String>> groups = new HashMap<>();\n\n        for(String email : emailToIdx.keySet()) {\n            int root = find(emailToIdx.get(email));\n            groups.computeIfAbsent(root, x -> new TreeSet<>()).add(email);\n        }\n\n        // Constructing the answer\n        List<List<String>> result = new ArrayList<>();\n\n        for(TreeSet<String> group : groups.values()) {\n            List<String> account = new ArrayList<>();\n            account.add(emailToName.get(group.first()));    // add name\n            account.addAll(group);  // add emails\n            result.add(account);\n        }\n\n        return result;\n    }\n\n    // Find operation with path compression\n    private int find(int node) {\n        while(parent[node] != node) {\n            node = parent[node];\n        }\n        return node;\n    }\n\n    // Union operation\n    private void union(int i, int j) {\n        int parentA = find(i);\n        int parentB = find(j);\n\n        if(parentA != parentB) {\n            parent[parentA] = parentB;\n        }\n    }\n}\n```\n\nPlease upvoe if you find it useful.\nHappy coding!
['Java']