Find Eventual Safe States

Problem Statement

In this scenario, we are working with a directed graph characterized by 'n' nodes, where each node has a unique identifier ranging from 0 to n - 1. The structure of this graph is represented by a 0-indexed 2D integer array named graph. In this array, graph[i] holds a list of nodes which direct edges emanate from node i to each node listed within graph[i].

Main concepts:

• Terminal Node: A node with no outbound edges leading to any other node.
• Safe Node: A node is dubbed "safe" if all paths originating from it invariably lead to a terminal node or another safe node.

The problem's goal is to identify and return all the nodes that are considered safe. The output should be an array of these safe nodes, organized in ascending order. This listing helps in verifying circuit designs or network routing configurations where certain safety conditions (deadlock or cycle-free paths) need assurance.

Examples

Example 1

Input:

graph = [[1,2],[2,3],[5],[0],[5],[],[]]

Output:

[2,4,5,6]

Explanation:

The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.

Example 2

Input:

graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]

Output:

[4]

Explanation:

Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.

Constraints

• n == graph.length
• 1 <= n <= 104
• 0 <= graph[i].length <= n
• 0 <= graph[i][j] <= n - 1
• graph[i] is sorted in a strictly increasing order.
• The graph may contain self-loops.
• The number of edges in the graph will be in the range [1, 4 * 104].

Approach and Intuition

Let's break down the process and underlying intuition through the examples provided:

1. Understanding Safe and Terminal Nodes:

   • A terminal node is straightforward; it's simply any node that doesn't point to another node.
   • A safe node, on the other hand, can only be considered safe if every single path that starts from it leads to another safe node or a terminal node.

2. General Steps to Solve the Problem:

   • Identify terminal nodes since these will be part of the output as they inherently meet the safety criteria by not having outbound edges.
   • Use depth-first search (DFS), or a similar graph traversal methodology, to track all the nodes from which terminal nodes are reachable.
   • During traversal, carefully mark nodes that potentially lead into cycles or nodes that do not eventually lead to terminal nodes. This can leverage marking or coloring nodes during DFS to represent different states (unvisited, visiting, safe).
   • Revisit each node, leveraging the markings to confirm if it either stays safe or leads to a terminal node through all possible paths.

By following these steps, we assess each node's connectivity and their eventual paths, thereby filtering out the nodes that inherently satisfy the safety conditions set by the problem statement.

Through examples:

• In Example 1, nodes like 5 and 6 are terminal. Node 2 eventually leads all paths to nodes 5 or 6, hence making it safe. Similar logic confirms the safety of the other nodes in the output.
• In Example 2, the only terminal node is 4. It is also the only safe node since all paths from node 4 lead to itself, meeting the terminal node condition directly.

The intuitive way of solving this problem primarily revolves around efficient graph traversal and a good mechanism for marking nodes based on their connectivity and the destination of their paths. This ensures that all potential pathways are accounted for when establishing the safety of each node.

Solutions

class Solution {
public:
    bool cycleDetected(int curr, vector<vector<int>>& graph, vector<bool>& visited,
             vector<bool>& recursionStack) {
        if (recursionStack[curr]) {
            return true;
        }
        if (visited[curr]) {
            return false;
        }
        visited[curr] = true;
        recursionStack[curr] = true;
        for (int next : graph[curr]) {
            if (cycleDetected(next, graph, visited, recursionStack)) {
                return true;
            }
        }
        recursionStack[curr] = false;
        return false;
    }
    
    vector<int> findSafeNodes(vector<vector<int>>& graph) {
        int totalNodes = graph.size();
        vector<bool> visited(totalNodes), recursionStack(totalNodes);
    
        for (int i = 0; i < totalNodes; i++) {
            cycleDetected(i, graph, visited, recursionStack);
        }
    
        vector<int> safeNodesList;
        for (int i = 0; i < totalNodes; i++) {
            if (!recursionStack[i]) {
                safeNodesList.push_back(i);
            }
        }
    
        return safeNodesList;
    }
};