802: Find-Eventual-Safe-States
Medium

My approach to this question was to use depth-first search. After running through the example test-cases, I came to the realisation that all nodes that either point to or exist in a cycle are unsafe (since if you keep on cycling through the loop, then you will never reach a terminal node).

Therefore, when we use DFS on every node (have to visit every edge to be able to determine which nodes are safe), we will have to maintain a runtime stack, to check what nodes you have seen inside the current recursive call, and a seen array, to check what nodes you have seen before (inside & outside of the current recursive call).

Then,

Finally, since we run DFS on every node, we will get a boolean value determining whether or not each node is safe or not and can just group these values into an array to return as our ans.

code

class Solution {
public:
    int dfs (int index, vector<vector<int>> &graph, vector<int> &stack, vector<int> &seen) {
        if (stack[index] == 1) {
            return 1;
        }

        if (seen[index] == 1) {
            return 0;
        }

        stack[index] = 1;
        seen[index] = 1;

        for (auto &node : graph[index]) {
            if (dfs(node, graph, stack, seen)) {
                return 1;
            }
        }

        stack[index] = 0;
        return 0;
    }

    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        vector<int> stack (graph.size(), 0);
        vector<int> seen (graph.size(), 0);

        vector<int> ans;
        for (int i = 0; i < graph.size(); ++i) {
            if(!dfs(i, graph, stack, seen)) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

complexity