C++ Union Find
See my latest update in repo LeetCode\n## Solution 1. Union Find\n\nGiven the constraints, a solution with O(R * B) is acceptable -- for each request, check if 
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n## Solution 1. Union Find\n\nGiven the constraints, a solution with `O(R * B)` is acceptable -- for each request, check if it obeys all the bans.\n\nFor the check, we can do it in `O(1)` time using UnionFind. For each prior valid requests, we connect the two friends. For a new request, we just need to check if the leaders of the two parties are in any of those bans.\n\n```cpp\n// OJ: https://leetcode.com/problems/process-restricted-friend-requests/\n// Author: github.com/lzl124631x\n// Time: O(R * B) where `R`/`B` is the length of `requests`/`bans`\n// Space: O(N)\nclass UnionFind {\n    vector<int> id;\npublic:\n    UnionFind(int n) : id(n) {\n        iota(begin(id), end(id), 0);\n    }\n    void connect(int a, int b) {\n        id[find(a)] = find(b);\n    }\n    int find(int a) {\n        return id[a] == a ? a : (id[a] = find(id[a]));\n    }\n    int connected(int a, int b) {\n        return find(a) == find(b);\n    }\n};\nclass Solution {\npublic:\n    vector<bool> friendRequests(int n, vector<vector<int>>& bans, vector<vector<int>>& requests) {\n        vector<bool> ans;\n        UnionFind uf(n);\n        for (auto &r : requests) {\n            int p = uf.find(r[0]), q = uf.find(r[1]); // the leaders of the two parties\n            bool valid = true;\n            if (!uf.connected(p, q)) { // Only need to check the bans if the two parties are not already connected\n                for (auto &b : bans) {\n                    int x = uf.find(b[0]), y = uf.find(b[1]); // the leaders of the two banned parties\n                    if ((x == p && y == q) || (x == q && y == p)) {\n                        valid = false;\n                        break;\n                    }\n                }\n            }\n            ans.push_back(valid);\n            if (valid) uf.connect(p, q); // connect two parties if request is valid\n        }\n        return ans;\n    }\n};\n```
[]