Union Find
I thought there is some clever way to track enemies, and wasted a lot of time. Should have looked at constraints closelly - 1000 is not a big number for a n * m
I thought there is some clever way to track enemies, and wasted a lot of time. Should have looked at constraints closelly - `1000` is not a big number for a `n * m` solution. \n\nSo we join frieds using union-find. But before we do, we scan through all `restrictions`, to make sure that sets of friends that we are joining do not include any restricted pair.\n\n**C++**\n```cpp\nint find(vector<int> &ds, int i) {\n    return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]);\n}\nvector<bool> friendRequests(int n, vector<vector<int>>& enemies, vector<vector<int>>& requests) {\n    vector<bool> res;\n    vector<int> ds(n, -1);\n    for (auto &req : requests) {\n        int i = find(ds, req[0]), j = find(ds, req[1]);\n        bool friends = i == j;\n        if (!friends) {\n            friends = true;\n            for (int k = 0; friends && k < enemies.size(); ++k) {\n                int x = find(ds, enemies[k][0]), y = find(ds, enemies[k][1]);\n                friends = (x != i || y != j) && (x != j || y != i);\n            }\n            if (friends)\n                ds[j] = i;\n        }\n        res.push_back(friends);\n    }\n    return res;\n}\n```
[]