[Python3] union-find
Edited on 9/7/2020. \n\nAs practicing more on LC, we realize the importance of union-find data structure. Even though there isn\'t a builtin implementatin in Py
Edited on 9/7/2020. \n\nAs practicing more on LC, we realize the importance of union-find data structure. Even though there isn\'t a builtin implementatin in Python, it is not difficult to do one from scratch. I have one [here](https://github.com/gaosanyong/algorithms/blob/master/unionfind.py) for reference. \n\nIn addition, I see lots of people taking part of union-find and mixing it along with the implementation of this problem. Personally, I prefer to start from a standard complete data structure. It is easier for developers to implment and easier for readers to understand. \n\n```\nclass UnionFind:\n    """A minimalist standalone union-find implementation."""\n    def __init__(self, n):\n        self.count = n               # number of disjoint sets \n        self.parent = list(range(n)) # parent of given nodes\n        self.rank = [1]*n            # rank (aka size) of sub-tree \n        \n    def find(self, p):\n        """Find with path compression."""\n        if p != self.parent[p]: \n            self.parent[p] = self.find(self.parent[p]) # path compression \n        return self.parent[p]\n    \n    def union(self, p, q):\n        """Union with ranking."""\n        prt, qrt = self.find(p), self.find(q)\n        if prt == qrt: return False\n        self.count -= 1 # one more connection => one less disjoint \n        if self.rank[prt] > self.rank[qrt]: prt, qrt = qrt, prt # add small sub-tree to large sub-tree for balancing\n        self.parent[prt] = qrt\n        self.rank[qrt] += self.rank[prt] # ranking \n        return True\n    \n        \nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        ufa = UnionFind(n) # for Alice\n        ufb = UnionFind(n) # for Bob\n        \n        ans = 0\n        edges.sort(reverse=True) \n        for t, u, v in edges: \n            u, v = u-1, v-1\n            if t == 3: ans += not (ufa.union(u, v) and ufb.union(u, v)) # Alice & Bob\n            elif t == 2: ans += not ufb.union(u, v)                     # Bob only\n            else: ans += not ufa.union(u, v)                            # Alice only\n        return ans if ufa.count == 1 and ufb.count == 1 else -1 # check if uf is connected \n```
['Python3']