Union Find | Python
Complexity\n- Time complexity: O(E*A(n)) where E=len(edges) and A(n)=inverse ackerman function\n\n- Space complexity: O(n)\n\n# Code\n\nclass UnionFind:\n    de
# Complexity\n- Time complexity: O(E*A(n)) where E=len(edges) and A(n)=inverse ackerman function\n\n- Space complexity: O(n)\n\n# Code\n```\nclass UnionFind:\n    def __init__(self,n):\n        self.par = [i for i in range(n+1)]\n        self.rank = [1]*(n+1)\n\n    def find(self,node):\n        while node!=self.par[node]:\n            self.par[node]=self.par[self.par[node]]\n            node = self.par[node]\n        return node\n\n    def union(self,n1,n2):\n        p1,p2 = self.find(n1),self.find(n2)\n\n        if p1==p2:\n            return 1\n        \n        if self.rank[p1]>self.rank[p2]:\n            self.rank[p1]+=self.rank[p2]\n            self.par[p2]=p1\n        else:\n            self.rank[p2]+=self.rank[p1]\n            self.par[p1]=p2\n\n        return 0\n\n\nclass Solution:\n    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n        alice,bob = UnionFind(n),UnionFind(n)\n        count = 0\n\n        for t,v1,v2 in edges:\n            if t==3:\n                count+=(alice.union(v1,v2)|bob.union(v1,v2))\n\n        for t,v1,v2 in edges:\n            if t==1:\n                count+=alice.union(v1,v2)\n            elif t==2:\n                count+=bob.union(v1,v2)\n   \n        return -1 if max(alice.rank)!=n or max(bob.rank)!=n else count\n```
['Union Find', 'Graph', 'Python', 'Python3']