[Python] Usual union find, explained.
The idea is that given problem constraints, we can allow to use union find. The idea is to traverse x, y in requests and check if we can make these persons frie
The idea is that given problem constraints, we can allow to use union find. The idea is to traverse `x, y in requests` and check if we can make these persons friends or not. We can make them if we do not have restrictions: we go through all restrictions and check that we do not have restriction for two given connected components.\n\n#### Complexity\nIt is `O(n * m * log(n))` for time and `O(n)` for space, where `m = len(requests)`.\n\n```python\nclass DSU:\n    def __init__(self, N):\n        self.p = list(range(N))\n\n    def find(self, x):\n        if self.p[x] != x:\n            self.p[x] = self.find(self.p[x])\n        return self.p[x]\n\n    def union(self, x, y):\n        xr = self.find(x)\n        yr = self.find(y)\n        self.p[xr] = yr\n\nclass Solution:\n    def friendRequests(self, n, restr, requests):\n        dsu, ans = DSU(n), []\n        for x, y in requests:\n            x_p, y_p = dsu.find(x), dsu.find(y)\n            bad = True\n            for a, b in restr:\n                a_p, b_p = dsu.find(a), dsu.find(b)\n                if set([a_p, b_p]) == set([x_p, y_p]):\n                    bad = False\n                    break\n                    \n            ans += [bad]\n            if bad: dsu.union(x, y)\n                \n        return ans\n```\n\nIf you have any questoins, feel free to ask. If you like the solution and explanation, please **upvote!**
['Union Find']