Medium
Remove Methods From Project — C++
Full explanation · Time O(n + e) · Space O(n + e)
// Time: O(n + e)
// Space: O(n + e)
// bfs
class Solution {
public:
vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
vector<vector<int>> adj(n);
const auto& bfs = [&]() {
vector<bool> lookup(n);
lookup[k] = true;
vector<int> q = {k};
while (!empty(q)) {
vector<int> new_q;
for (const auto& u : q) {
for (const auto& v : adj[u]) {
if (lookup[v]) {
continue;
}
lookup[v] = true;
new_q.emplace_back(v);
}
}
q = move(new_q);
}
return lookup;
};
for (const auto& e : invocations) {
adj[e[0]].emplace_back(e[1]);
}
const auto& lookup = bfs();
for (const auto& e : invocations) {
if (lookup[e[0]] != lookup[e[1]]) {
vector<int> result(n);
iota(begin(result), end(result), 0);
return result;
}
}
vector<int> result;
for (int u = 0; u < n; ++u) {
if (!lookup[u]) {
result.emplace_back(u);
}
}
return result;
}
};