[Python] Union find beats 98% runtime and 34% space
I think it is easy for everyone to see this problem requires union find. \nThe key point is about how to detect if the friend request is restricted or not. \nWe
I think it is easy for everyone to see this problem requires union find. \nThe key point is about how to detect if the friend request is restricted or not. \nWe can of course iterate through all restricted ones and check, but that will be too expensive. \nHere I have maintained a map called `excluded`, which is `{people => { set of restricted peoples } }`.\nThis map is updated whenever a successful union happens.\nWe use `DisjointSet` to keep the information of friend circles, like everyone would do.\n\nSo the algorithm has only 3 conditions for people1 trying to make friend with people2:\n1. people1 and people2 are already in the same group (directly or indirectly), that is just fine. `res = True`\n2. people2 is in people1\'s excluding list, then they cannot be friends. `res = False`\n3. people1 and people2 are not in the same friend circle, and they are not mutually excluded, then we just merge their friend circles. The merge happens by updating the excluded map (more details in the next paragraph) and DisjointSet. `res = True`\n\nThe excluded map update is straight forward, it does 2 things to update:\n1. Merge names from people2\'s list to people1\'s list. Because people1 and people2 are in the same group now, and the excluded people should be merged.\n2. For every people excluded by people2, they also exclude people2, and we need them to exclude people1 as well\n\nHere is the code:\n```python\nclass DisjointSet:\n    def __init__(self, n):\n        self.parent = list(range(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\nclass Solution:\n    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n        from collections import defaultdict\n        excluded = defaultdict(set)\n        for people1, people2 in restrictions: # exclusion is mutual\n            excluded[people1].add(people2) \n            excluded[people2].add(people1)\n\t\t\t\n        def update_exclusion(from_p, to_p): # update exclusion map\n            targets = excluded.pop(from_p, [])\n            for people in targets: # people being excluded by people2 should now also exclude people1\n                excluded[people].remove(from_p)\n                excluded[people].add(to_p)\n            excluded[to_p].update(targets) # people1 should exclude people that are excluded by people2\n\t\t\t\n        res = []\n        disjoint_set = DisjointSet(n)\n        for people1, people2 in requests:\n            circle1 = disjoint_set.find(people1)\n            circle2 = disjoint_set.find(people2)\n            if circle1 == circle2: \n                res.append(True)\n            elif circle2 in excluded[circle1]:\n                res.append(False)\n            else:\n                update_exclusion(circle2, circle1)\n                disjoint_set.parent[circle2] = circle1\n                res.append(True)\n        return res\n                \n```
['Union Find']