python 3 - DSU + union by rank + path compression
Intuition\nAs long as you know DSU, this question is quite straghtforward.\n\nProcess edges in 2 parts:\n- Join all type 3 edges and then type 1 edges. This den
# Intuition\nAs long as you know DSU, this question is quite straghtforward.\n\nProcess edges in 2 parts:\n- Join all type 3 edges and then type 1 edges. This denotes all Alice edges. And edges with the same parent can be removed.\n- Same process will be done by using type 2 edges instead of type 1.\n\nCheck if all nodes belong to the same parent finally to see if any nodes cannot be reached.\n\n# Approach\nDSU\n\n# Complexity\n- Time complexity:\nO(n * alpha(n)) -> DSU operation on input edges list\n\n- Space complexity:\nO(n) -> DSU structure\'s sc\n\n# Code\n```\nclass DSU:\n    def __init__(self, n):\n        self.par = list(range(n))\n        self.rank = [1] * n\n    \n    def find(self, node):\n        if self.par[node] != node:\n            self.par[node] = self.find(self.par[node])\n        return self.par[node]\n    \n    def union(self, x, y):\n        px, py = self.find(x), self.find(y)\n        if self.rank[px] > self.rank[py]: # py to px\n            self.par[py] = px\n            self.rank[px] += self.rank[py]\n        else: # px to py\n            self.par[px] = py\n            self.rank[py] += self.rank[px]\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        import collections\n        type2edge = collections.defaultdict(list)\n        for ty, u, v in edges:\n            type2edge[ty].append([u, v])\n        \n        ans = 0\n\n        # alice\n        dsua = DSU(n+1)\n        for u, v in type2edge[3]: # join common\n            if dsua.find(u) == dsua.find(v):\n                ans += 1\n            else:\n                dsua.union(u, v)\n        for u, v in type2edge[1]:\n            if dsua.find(u) == dsua.find(v):\n                ans += 1\n            else:\n                dsua.union(u, v)\n        \n        for i in range(n):\n            dsua.find(i)\n        if len(set(dsua.par[1:])) > 1: # diff groups\n            return -1\n        \n        # bob\n        dsub = DSU(n+1)\n        for u, v in type2edge[3]:\n            if dsub.find(u) != dsub.find(v):\n                dsub.union(u, v)\n        for u, v in type2edge[2]:\n            if dsub.find(u) == dsub.find(v):\n                ans += 1\n            else:\n                dsub.union(u, v)\n        \n        for i in range(n):\n            dsub.find(i)\n        if len(set(dsub.par[1:])) > 1:\n            return -1\n        \n        return ans\n```
['Union Find', 'Python3']