Description

Submission

class Solution {
    vector<int> visited;  // 0: not visited, 1: current round, visited in another round

    bool dfs(int node, vector<vector<int>>& graph) {
        if(visited[node] == 2) return true;
        if(visited[node] == 1) return false;
        visited[node] = 1;

        for(auto x: graph[node]) {
            if(!dfs(x, graph)) return false;
        }

        visited[node] = 2;

        return true;
    }
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        int n = graph.size();
        visited.resize(n, 0);
        vector<int> rets;

        for(int i = 0; i < n; ++i) {
            if(dfs(i, graph)) rets.push_back(i);
        }

        sort(rets.begin(), rets.end());

        return rets;
    }
};

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        queue<int> q;
        int n = graph.size();
        vector<int> outDegree(n);

        vector<vector<int>> rGraph(n);  // the reversed graph

        for(int i = 0; i < n; ++i) {
            outDegree[i] = graph[i].size();
            for(auto x: graph[i]) {
                rGraph[x].push_back(i);
            }
            if(!outDegree[i]) q.push(i);
        }

        vector<int> rets;
        while(!q.empty()) {
            int cur = q.front();
            q.pop();

            rets.push_back(cur);

            for(auto x: rGraph[cur]) {
                --outDegree[x];
                if(!outDegree[x]) {
                    q.push(x);
                }
            }
        }

        sort(rets.begin(), rets.end());

        return rets;    
    }
};