[Python] Union Find [350ms, 15MB]
python\nclass UnionFind:\n    def __init__(self, bans, n):\n        self.bans = bans # people that are banned inside union\n        self.people = [set([i]) for 
``` python\nclass UnionFind:\n    def __init__(self, bans, n):\n        self.bans = bans # people that are banned inside union\n        self.people = [set([i]) for i in range(n)]  # people inside union\n        self.parent = [i for i in range(n)] # parent of each person \n        self.r = [1 for i in range(n)] # rank in union\n        \n    def find(self, x):\n        if self.parent[x] != x:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n    \n    def union(self, x, y):\n        x_p = self.find(x)\n        y_p = self.find(y)\n        if x_p == y_p:\n            return True\n        if self.r[y_p] > self.r[x_p]: # Path compression by rank\n            x_p, y_p = y_p, x_p\n            \n\t\t# Check if does union x_p, y_p have people in ban\n\t\t\n        for person in self.bans[y_p]: \n            if person in self.people[x_p]:\n                return False\n        \n        for person in self.bans[x_p]:\n            if person in self.people[y_p]:\n                return False\n        \n\t\t# Update all people, rank, ban, parent in y_p to x_p\n        self.r[x_p] += self.r[y_p]\n        self.people[x_p].update(self.people[y_p])\n        self.bans[x_p].update(self.bans[y_p])\n        self.parent[y_p] = x_p\n        return True\n        \n\nclass Solution:\n    def friendRequests(self, n: int, bans: List[List[int]], requests: List[List[int]]) -> List[bool]:\n        banGraph = [set() for i in range(n)]\n        for x, y in bans:\n            banGraph[x].add(y)\n            banGraph[y].add(x)\n        uf = UnionFind(banGraph, n)\n        result = []\n        for x,y in requests:\n            result.append(uf.union(x, y))\n        return result\n```\n
['Union Find', 'Python']