Union Find | Python / JS Solution
Hello Tenno Leetcoders,\nFor this problem, Alice and Bob have an undirected graph with n nodes, where each node represents a point in the graph. The graph has t
Hello **Tenno Leetcoders**,\nFor this problem, Alice and Bob have an undirected graph with n nodes, where each node represents a point in the graph. The graph has three types of edges:\n\n1) Type 1: These edges can only be traversed by Alice.\n\n2) Type 2: These edges can only be traversed by Bob.\n\n3) Type 3: These edges can be traversed by both Alice and Bob.\n\nWe are asked to find the `maximum number of edges` that can be removed from the graph such that after removing the edges, Alice and Bob can still traverse the graph fully, meaning starting from any node, Alice and Bob can still reach all other nodes.\n\nYou are given an array edges, where `edges[i] = [typei, ui, vi]` represents a bidirectional edge of type `typei` between nodes `ui` and `vi`. \n\nif we have `edges[i] = [1, 2, 3]`, this represent that there is a `Type 1` edge between `nodes 2` and `3`, and Alice can traverse this edge.\n\nWe want to find `the maximum number of edges that can be removed` such that the graph can still be fully traversed by both Alice and Bob or return -1 if it is not possible to traverse the graph fully even after removing some edges\n\n### Explanation\n\nThe idea behind this problem is to keep track of which edges Alice and Bob can iterate separately and which edges both of them can iterate together. For this approach, we can use three different `Union Find`. For each of the three types of edges, we can create three different instances of Union Find\n\nWe will traverse through the edges and use these Union Find instances to keep track of the connected component for each type of edge separately.\n\nFor each `Type`, we will call `union() method`:\n\n- Type 1 will be called for Alice to merge componenet containing u and v\n\n- Type 2 will be called for Bob to merge corresponding components\n\n- Type 3 will be called for Alice and Bob to merge the componenets for both, since the edges can be traveled by both\n\nWith all the edges already processed, we need to check if Alice and Bob can traverse the entire graph by checking the number of connected components in both `Union Find` instance will be equal to one.\n\nIf both can travel the entire graph, we can start removing edges to see how many can be removed while still being able to traverse the graph\n\nThen we traverse through the edges counting type 3 edges that were merged by both Alice and Bob, and as well for type 1 and type 2 edges that was merged by either Alice or Bob\n\nWe can then check if both can traverse the graph by checking if they have more than one connected component\n\nIf either Alice or Bob has more than one connected component, then it means that there are some vertices that are not reachable by either Alice or Bob as the problem\'s requirement should be able to remove edges such that all vertices are reachable by both of them. \n\nTherefore, if there is more than one connected component for either Alice or Bob, we return -1 to indicate that it is not possible to remove edges to satisfy the requirement.\n\nThe `maximum number of edges that can be removed` while still being able to fully traversed by both will be the sum of the counts of `type1, type2 and type3 edges` denoted as `alice_remove, bob_remove, both_remove` or `return -1` as they were not able to traverse the whole graph\n\n\n### Code\n\n**Python**\n\n```\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = [i for i in range(n + 1)]\n        self.size = [1] * (n + 1)\n        self.components = n\n\n    def find(self, x):\n        # If the parent of x is not x, recursively find the parent of x\n        if self.parent[x] != x: self.parent[x] = self.find(self.parent[x])\n        # Return the parent of x\n        return self.parent[x]\n\n    def union(self, x, y):\n        # Find the parents of x and y\n        x_root = self.find(x)\n        y_root = self.find(y)\n        # If the parents are the same, x and y are already in the same component\n        if x_root == y_root: return False\n        # Merge the smaller component into the larger component\n        if self.size[x_root] < self.size[y_root]: x_root, y_root = y_root, x_root\n        self.size[x_root] += self.size[y_root]\n        self.parent[y_root] = x_root\n        self.components -= 1\n        return True\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        alice = UnionFind(n)\n        bob = UnionFind(n)\n        both = UnionFind(n)\n        alice_remove = bob_remove = both_remove = 0\n\n        # Process type 3 edges\n        for t, u, v in edges:\n            if t == 3:\n                if both.union(u, v):\n                    alice.union(u, v)\n                    bob.union(u, v)\n                else:\n                    both_remove += 1\n        \n        # Process type 1 edges\n        for t, u, v in edges:\n            if t == 1:\n                if not alice.union(u, v):\n                    alice_remove += 1\n        \n        # Process type 2 edges\n        for t, u, v in edges:\n            if t == 2:\n                if not bob.union(u, v):\n                    bob_remove += 1\n        \n        # Check if both Alice and Bob can traverse the graph\n        if alice.components > 1 or bob.components > 1:\n            return -1\n        \n        return alice_remove + bob_remove + both_remove\n```\n\n\n\n**JavaScript**\n\n```\n/**\n * @param {number} n\n * @param {number[][]} edges\n * @return {number}\n */\n\nclass UnionFind{\n    \n    constructor(n){\n        this.parent = Array.from({length: n+1}, (_,i) => i)\n        this.size = Array(n+1).fill(1);\n        this.components = n\n    }\n    \n    find(x) {\n        return this.parent[x] !== x ? this.parent[x] = this.find(this.parent[x]) : this.parent[x];\n    }\n    \n    union(x,y){\n        const rootX = this.find(x)\n        const rootY = this.find(y)\n        \n        if(rootX === rootY) return false\n        const [smaller, bigger] = this.size[rootX] < this.size[rootY] ? [rootX, rootY] : [rootY, rootX];\n  \n        this.size[smaller] += this.size[bigger];\n        this.parent[bigger] = smaller;\n        this.components -= 1    \n        return true\n    }\n    \n}\n\n\nvar maxNumEdgesToRemove = function(n, edges) {\n    const alice = new UnionFind(n);\n    const bob = new UnionFind(n);\n    const both = new UnionFind(n);\n    let aliceRemove = 0, bobRemove = 0, bothRemove = 0;\n\n    // Process type 3 edges\n    for(const [type, u, v] of edges){\n        if(type === 3){\n            both.union(u,v) ? (alice.union(u,v), bob.union(u,v) ): bothRemove +=1 \n        }\n    }\n\n    // Process type 1 edges\n    for(const[type, u,v] of edges){  \n        if(type === 1)\n            !alice.union(u, v) && aliceRemove++\n        }\n\n    // Process type 2 edges\n    for(const[type, u,v] of edges){  \n        if(type === 2){\n            !bob.union(u, v) && bobRemove++ \n        }\n    }\n    \n    // Check if both Alice and Bob can traverse the graph\n    if(alice.components > 1 || bob.components > 1) return -1\n    \n    return aliceRemove + bobRemove + bothRemove\n};\n```\n\n#### Time Complexity: O(m*\u03B1(n))\n\nUnion-Find algorithm with union-by-rank and path compression is `O(m\u03B1(n))` where n is the number of elements and m is the number of operations.  `\u03B1(n)` is the inverse Ackermann function, which grows very slowly and is effectively constant for practical values of n.\n\n#### Space Complexity: O(n)\n\nwhere n is the number of vertices in the graph, because we need to store the parent and size arrays for each Union-Find data structure.\n\n \n***Warframe\'s Darvo wants you to upvote this post  \uD83D\uDE4F\uD83C\uDFFB \u2764\uFE0F\u200D\uD83D\uDD25***\n\n![image](https://assets.leetcode.com/users/images/814f5668-c966-46d7-ba42-e5435c4c1761_1675302761.3081913.gif)
['Union Find', 'Python', 'JavaScript']