Find Eventual Safe States

Leetcode Problem:

• Find Eventual Safe States

Summary

• Finding safe nodes in a directed graph

Approach

• Breadth-First Search (BFS) algorithm is used to detect safe nodes in the graph
• The graph is represented as an adjacency list, and a queue is used to keep track of nodes to visit
• Each node's out-degree is calculated and used to determine which nodes to add to the queue first.

Complexity

• O(N + E)

Explanation

• The solution starts by initializing variables to keep track of the graph, out-degrees, safe nodes, and an answer list
• It then iterates over the graph to calculate the out-degrees of each node and adds nodes with an out-degree of 0 to the queue
• The BFS algorithm is then used to traverse the graph, marking nodes as safe as they are visited
• Finally, the solution iterates over the graph again to add safe nodes to the answer list.

Solution Code:

class Solution {
public:
    vector eventualSafeNodes(vector>& G) {
        int N = G.size();
        vector> R(N);
        vector outdegree(N), safe(N), ans;
        queue q;
        for (int i = 0; i < N; ++i) {
            for (int v : G[i]) {
                R[v].push_back(i);
            }
            outdegree[i] = G[i].size();
            if (outdegree[i] == 0) q.push(i);
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            safe[u] = 1;
            for (int v : R[u]) {
                if (--outdegree[v] == 0) q.push(v);
            }
        }
        for (int i = 0; i < N; ++i) {
            if (safe[i]) ans.push_back(i);
        }
        return ans;
    }
};