[C++] O(1) to check all restrictions Beats 100.00%
Intuition\nUse DisJoinSet to check circle. Maintain likes and unlikes for each node;\n\n# Approach\n Describe your approach to solving the problem. \n1. If we c
# Intuition\nUse DisJoinSet to check circle. Maintain likes and unlikes for each node;\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. If we can know the like and unlike nodes, we can process all restrictions at once.\n2. Before union (making friend), we need to check no conflic beteen unlikes and likes.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    class DJS {\n    public:\n        vector<int> parent, size;\n        vector<bitset<1000>> like, unlike;\n        DJS(int n, const vector<vector<int>>& restrictions) {\n            parent.resize(n);            \n            like.resize(n);\n            unlike.resize(n);            \n            size.resize(n);\n            fill(size.begin(), size.end(), 1);\n            for (int i = 0; i < n; i++) {\n                parent[i] = i;\n                like[i][i] = true;\n            }\n            for (auto& r : restrictions) {\n                unlike[r[0]][r[1]] = true;\n                unlike[r[1]][r[0]] = true;\n            }\n        }\n        int find(int a) {\n            int node = a;\n            while (node != parent[node]) {\n                node = parent[node];\n            }\n            return parent[a] = node;\n        }\n        bool unionBySize(int a, int b) {\n            int pa = find(a), pb = find(b);\n            if (pa == pb) return true;\n            // we need to check no conflic beteen unlikes and likes.\n            if ((unlike[pa] & like[pb]).any() || (unlike[pb] & like[pa]).any()) {\n                return false;\n            }\n            int lead = pb, follow = pa;\n            if (size[pa] > size[pb]) {\n                lead = pa;\n                follow = pb;\n            }        \n            parent[follow] = lead;\n            size[lead] += size[follow];\n            like[lead] |= like[follow];\n            unlike[lead] |= unlike[follow];\n            return true;\n        }\n    };\n    vector<bool> friendRequests(int n, vector<vector<int>>& restrictions, vector<vector<int>>& requests) {\n        DJS djs(n, restrictions);\n        int m = requests.size();\n        vector<bool> ans(m);\n        for (int i = 0; i < m; i++) {\n            ans[i] = djs.unionBySize(requests[i][0], requests[i][1]);\n        }\n        return ans;\n    }\n};\n\n\n\n```
['C++']