Medium

Remove Methods From ProjectC++

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;
    }
};