Python union find with detailed explanation
Use the union find algorithm. The critical part is all about the restrictions. When there are too many people and too many restrictions, it will be time-consumi
Use the union find algorithm. The critical part is all about the restrictions. When there are too many people and too many restrictions, it will be time-consuming to check each restriction, before answering a request. We know that union is kind of a hierarchy system, where everyone has a supervisor (better than the usually known "parent").\n\nIt would good to let the supervisors to handle the restrictions. If A dislike B, let A\'s supervisor dislike B\'s supervisor. Since initially everyone supervises oneself, the given restrictions are a good start. We build a Hash map to handle the restrictions. \n\nFor a coming request, we only check the two supervisors. If they do not dislike each other, the relation can be built\nand call union()! During the union process, one supervisor SA retires and the other supervisor SB remains, and also supervises SA. In addition to the union itself, there are two important things to do:\n1) Go through everyone that SA dislikes, let each dislike SB (, who now supervises SA), instead of SA.\n2) SB should take all the restrictions that SA are involved in. One can pop SA from the map, since he  does not bother this kind of nonsense any more. \n\n```\nclass Solution:\n    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n        rst = defaultdict(set)\n        for a, b in restrictions:\n            rst[a].add(b)\n            rst[b].add(a)\n        del restrictions\n        ans = []\n        supervisor = [i for i in range(n)]\n        def find(x):\n            if supervisor[x] == x:\n                return x\n            else:\n                supervisor[x] = find(supervisor[x])\n                return supervisor[x]\n\n        def union(x, y):                # the method is more than the conventional union() method\n            x, y = find(x), find(y)\n            if x > y:\n                x, y = y, x\n            supervisor[y] = x           # "y", who was a supervisor, retires. "x" becomes his supervisor.\n            rst[y] = rst.get(y, set())  # persons who "y", as well as his group, does not like\n            for z in rst[y]:            # for each of those persons\n                rst[z].remove(y)        # stop hating "y"\n                rst[z].add(x)           # hate his supervisor instead\n            if x not in rst:            # "x" consider everyone who "y" and his group do not like\n                rst[x] = set()\n            rst[x] |= rst.pop(y)\n            return\n\t\t\t\n        for a, b in requests:               # process each request\n            sa, sb = find(a), find(b)       # approach the two supervisors\n            if sa == sb:                    # they are the same, meaning that a and b are already friends\n                ans.append(True)\n            elif sb in rst.get(sa, set()):  # if the supervisors do not permit\n                ans.append(False)\n            else:                           # if the supervisors permit\n                ans.append(True)\n                union(a, b)                 # build the relation\n        return ans\n```
[]