Hash Table + Union Find | 661 ms - faster than 71.86% solutions
Complexity\n- Time complexity: O(m \cdot\log(m) + k \cdot m \cdot \alpha(n))\n- Space complexity: O(n + m + k)\n\nwhere m = restrictions.length, k = requests.le
# Complexity\n- Time complexity: $$O(m \\cdot\\log(m) + k \\cdot m \\cdot \\alpha(n))$$\n- Space complexity: $$O(n + m + k)$$\n\nwhere `m = restrictions.length, k = requests.length`,\n$\\alpha(n)$ is inverse Ackermann function ([wiki](https://en.wikipedia.org/wiki/Ackermann_function#Inverse)).\n\nBecause `n < 1000, m < 1000, k < 1000`, let `p = max(n, m, k)`.\n\n- Time complexity: $$O(p^2 \\cdot \\alpha(p))$$\n- Space complexity: $$O(p)$$\n\n# Code\n``` python3 []\nclass DJS:\n    def __init__(self, n):\n        self._d = list(range(n))\n    \n    def find(self, a):\n        aa = self._d[a]\n        if a == aa:\n            return aa\n        self._d[a] = self.find(aa)\n        return self._d[a]\n\n    def union(self, a, b):\n        aa = self.find(a)\n        bb = self.find(b)\n        if aa != bb:\n            self._d[aa] = bb\n\nclass Solution:\n    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n        pairs = defaultdict(set)\n        for x, y in sorted(restrictions):\n            x, y = min(x, y), max(x, y)\n            pairs[x].add(y)\n        \n        djs = DJS(n)\n\n        def check(uu, vv):\n            for x, ys in pairs.items():\n                xx = djs.find(x)\n                if xx != uu and xx != vv:\n                    continue\n                for y in ys:                \n                    yy = djs.find(y)\n                    if yy == uu or yy == vv:\n                        return False\n            return True\n\n        result = []\n        for u, v in requests:               \n            uu = djs.find(u)\n            vv = djs.find(v)\n            if uu == vv:\n                result.append(True)\n                continue\n            \n            current = check(uu, vv)\n            result.append(current)\n            if current:\n                djs.union(uu, vv)\n        \n        return result\n\n```
['Hash Table', 'Union Find', 'Graph', 'Python3']