🔥Very Easy✅|| Full Explanation || Union✅≧◠‿◠≦✅||🧠Less Memory || O(nlogn) Time
Intuition\nTo solve this problem, we can use the Union-Find (Disjoint Set Union, DSU) data structure. The goal is to ensure that both Alice and Bob can traverse
# Intuition\nTo solve this problem, we can use the Union-Find (Disjoint Set Union, DSU) data structure. The goal is to ensure that both Alice and Bob can traverse the entire graph while maximizing the number of edges removed.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n---\n\n\n# Approach \nThe steps are as follows:\n\n1. **Sort and Prioritize Edges**: Process type 3 edges first since they can be used by both Alice and Bob. Then, process type 1 and type 2 edges separately.\n\n2. **Union-Find Setup**: Maintain two separate Union-Find structures, one for Alice and one for Bob.\n\n3. **Union Operation**: Apply union operations to both Union-Find structures for type 3 edges. Then apply union operations for type 1 edges to Alice\'s Union-Find and type 2 edges to Bob\'s Union-Find.\n\n4. **Check Connectivity**: After processing all edges, check if both Alice and Bob can reach all nodes (i.e., the Union-Find structures should have exactly one connected component).\n\n5. **Count Removed Edges**: Keep track of the number of edges that were not used in the union operations.\n<!-- Describe your approach to solving the problem. -->\n\n---\n\n\n# Complexity\n- Time complexity: $$O(nlogn)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n+m)$$ \n                - where n is the number of nodes and m is the number of edges.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n\n\n# Code\n```\nfrom typing import List\n\nclass UnionFind:\n    def __init__(self, n):\n        self.parent = list(range(n))\n        self.rank = [1] * n\n        self.count = n\n\n    def find(self, u):\n        if self.parent[u] != u:\n            self.parent[u] = self.find(self.parent[u])  # Path compression\n        return self.parent[u]\n\n    def union(self, u, v):\n        root_u = self.find(u)\n        root_v = self.find(v)\n        if root_u != root_v:\n            if self.rank[root_u] > self.rank[root_v]:\n                self.parent[root_v] = root_u\n            elif self.rank[root_u] < self.rank[root_v]:\n                self.parent[root_u] = root_v\n            else:\n                self.parent[root_v] = root_u\n                self.rank[root_u] += 1\n            self.count -= 1\n            return True\n        return False\n\n    def connected_components(self):\n        return self.count\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        uf_alice = UnionFind(n)\n        uf_bob = UnionFind(n)\n        \n        edges.sort(reverse=True, key=lambda x: x[0])\n        \n        used_edges = 0\n\n        for edge_type, u, v in edges:\n            u -= 1\n            v -= 1\n            if edge_type == 3:\n                if uf_alice.union(u, v) | uf_bob.union(u, v):\n                    used_edges += 1\n            elif edge_type == 1:\n                if uf_alice.union(u, v):\n                    used_edges += 1\n            elif edge_type == 2:\n                if uf_bob.union(u, v):\n                    used_edges += 1\n        \n        if uf_alice.connected_components() > 1 or uf_bob.connected_components() > 1:\n            return -1\n        \n        return len(edges) - used_edges\n  \n```\n\n---\n\n\n# Explanation:\n- **Union-Find Initialization**: Two Union-Find structures are created, one for Alice and one for Bob.\n- **Processing Type 3 Edges**: These edges are used by both Alice and Bob. We perform the union operation on both Union-Finds.\n- **Processing Type 1 and Type 2 Edges**: Type 1 edges are used for Alice\'s Union-Find, and Type 2 edges are used for Bob\'s Union-Find.\n- **Connectivity Check**: After processing all edges, we check if both Alice and Bob can traverse all nodes by ensuring each Union-Find has exactly one connected component.\n- **Counting Removed Edges**: The difference between the total number of edges and the number of edges used gives the number of edges that can be removed.\n- \n---\n\n![ae7b6a0f-bc82-4c50-bede-27cdbb032188_1718672884.964757.png](https://assets.leetcode.com/users/images/b57dfde7-8584-4934-ad17-ecf59bfa11ad_1719716465.0862072.png)\n\n---\n\n> Thank You
['Union Find', 'Graph', 'Python3']