Python UnionFind 87% faster avg O(E+R) with Explaination
Correct me if I am wrong but the time complexity I think would be O(N + ER) on worst case and O(N+E+R) on average case where E is number of requests and R is nu
Correct me if I am wrong but the time complexity I think would be O(N + ER) on worst case and O(N+E+R) on average case where E is number of requests and R is number of restrictions. And the space complexity is O(N+R). Basically we will keep track of all the root of restrictions from in each root node in union find. \n\nWhen we are adding (x, y) the request we will check if there is restriction between root_of_x and root_of_y. If there are restrictions we will return False.\n\nIf nodes can be friends, we will add those nodes by union by rank and keep track of root and child between those root_of_x and root_of_y.\n\nSuppose when we did the union root = root_of_x and child = root_of_y, then, we will loop through all the restrictions in root_of_y and try to find their root in the graph and add that root to the restriction of root_of_x. Then we will delete the restriction of root_of_y.\n\nThis way when we are doing union, the restrictions will be merged. \n```\nclass Solution:\n    def friendRequests(self, n: int, restrictions: List[List[int]], requests: List[List[int]]) -> List[bool]:\n        \n        union_find = UnionFind(n, restrictions)\n        result = []\n        for u, v in requests:\n            if union_find.union(u, v):\n                result.append(True)\n            else:\n                result.append(False)\n        return result\n            \nclass UnionFind:\n    def __init__(self, n, restricts):\n        self.root = [i for i in range(n)]\n        self.rank = [1 for i in range(n)]\n        self.restrictions = {}\n        for u, v in restricts:\n            if u not in self.restrictions:\n                self.restrictions[u] = set()\n            if v not in self.restrictions:\n                self.restrictions[v] = set()\n            self.restrictions[u].add(v)\n            self.restrictions[v].add(u)\n        \n    def find(self, x):\n        if self.root[x] != x:\n            self.root[x] = self.find(self.root[x])\n        return self.root[x]\n    def union(self, x, y):\n        root_x = self.find(x)\n        root_y = self.find(y)\n        if (root_x in self.restrictions and root_y in self.restrictions[root_x]) or (root_y in self.restrictions and root_x in self.restrictions[root_y]):\n            return False\n        \n        if root_x != root_y:\n            root, child = root_y, root_x\n            if self.rank[root_x] < self.rank[root_y]:\n                self.root[root_x] = root_y\n            elif self.rank[root_y] < self.rank[root_x]:\n                self.root[root_y] = root_x\n                root, child = root_x, root_y\n            else:\n                self.root[root_x] = root_y\n                self.rank[root_y] += 1\n            if child in self.restrictions:\n                for rest in self.restrictions[child]:\n                    if root not in self.restrictions:\n                        self.restrictions[root] = set()\n                    self.restrictions[root].add(self.find(rest))\n                del self.restrictions[child]\n        return True\n```
['Union Find', 'Python']