[Python] Simple Union Find
Things we know:\n1. We know how to solve a problem if edges only contains type3 edges. The solusion will be: get a spanning tree, then all the other edges can b
Things we know:\n1. We know how to solve a problem if edges only contains **type3** edges. The solusion will be: get a spanning tree, then all the other edges can be removed as the spanning tree already connected all nodes.\n2. We know **type3** edge is important becasues: **type3** edge can connect both for **Alice** and **Bob** in best case. But **type1** and **type2** edge can only connect **Alice** or **Bob** in best case.\n\nThen our idea will be:\n1. Use spanning tree algoritm to choose from **type3** edges first (**Union Find**): If two nodes are not from the same **union**, connect them\n2.  Then use **type1** edges for **Alice**\n3.  Use **type2** edges for Bob\n4.  Finnaly if they are still not connected, return **-1**\n\n```\nclass UnionFind(object):\n    def __init__(self, size):\n        self.res = [i for i in range(size)]\n        self.group = size\n        self.size = [1] * size\n\n    def find(self, child):\n        if self.res[child] != child:\n            idx = self.find(self.res[child])\n            self.res[child] = idx\n        return self.res[child]\n\n    def union(self, a, b):\n        pa = self.find(a)\n        pb = self.find(b)\n        if pa == pb:\n            return\n        if self.size[pa] > self.size[pb]:\n            pa, pb = pb, pa\n        self.group -= 1\n        self.res[pa] = pb\n        self.size[pb] += self.size[pa]\n        \nclass Solution(object):\n    def maxNumEdgesToRemove(self, n, edges):\n        """\n        :type n: int\n        :type edges: List[List[int]]\n        :rtype: int\n        """\n\t\t# used edges count\n        res = 0\n        ua = UnionFind(n + 1)\n        ub = UnionFind(n + 1)\n        es = [[] for _ in range(4)]\n        \n\t\t# group edges\n        for edge in edges:\n            es[edge[0]].append(edge)\n            \n\t\t# use type 3 first\n        for edge in es[3]:\n            x = ua.find(edge[1])\n            y = ua.find(edge[2])\n\t\t\t\n\t\t\t# if not from same union, add the edge and connect them\n            if x != y:\n                res += 1\n                ua.union(x, y)\n                ub.union(x, y)\n\n        for edge in es[2]:\n            x = ua.find(edge[1])\n            y = ua.find(edge[2])\n            if x != y:\n                res += 1\n                ua.union(x, y)\n                \n        for edge in es[1]:\n            x = ub.find(edge[1])\n            y = ub.find(edge[2])\n            if x != y:\n                res += 1\n                ub.union(x, y)\n\t\t# if still not connected, return -1\n        x = ua.find(1)\n        if any(x != ua.find(i) for i in range(1, n + 1)):\n            return -1\n            \n\t\tx = ub.find(1)\n        if any(x != ub.find(i) for i in range(1, n + 1)):\n            return -1\n\n        return len(edges) - res\n```
['Union Find', 'Python']