802.cpp

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<State> states(graph.size(), UNKNOWN);
        vector<int> ans;
        for(int i = 0; i < graph.size(); i++) {
            if (dfs(graph, i, states) == SAFE) {
                ans.push_back(i);
            }
        }
        return ans;
    }
private:
    enum State {UNKNOWN, VISITING, SAFE, UNSAFE};
    State dfs(const vector<vector<int>>& g, int curr, vector<State>& states) {
        if (states[curr] == VISITING) {
            return states[curr] = UNSAFE;
        }
        if (states[curr] != UNKNOWN) {
            return states[curr];
        }
        states[curr] = VISITING;
        for (int next : g[curr]) {
            if (dfs(g, next, states) == UNSAFE)
                return states[curr] = UNSAFE;
        }
        return states[curr] = SAFE;
    }
};