802. Find Eventual Safe States

[mah-shamim]

Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an integer array of nodes adjacent to node i, meaning there is an edge from node i to each node in graph[i].

A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).

Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

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].

[mah-shamim]

We need to identify all the safe nodes in the graph. This involves checking if starting from a given node, every path eventually reaches a terminal node or another safe node. The solution uses Depth-First Search (DFS) to detect cycles and classify nodes as safe or unsafe.

Key Insights:

1. Terminal Nodes: A node with no outgoing edges is a terminal node.
2. Safe Nodes: A node is safe if, starting from that node, all paths eventually lead to terminal nodes or other safe nodes.
3. Cycle Detection: If a node is part of a cycle, it's not a safe node because paths starting from it won't lead to terminal nodes.

Approach:

• We use DFS to explore each node and determine if it’s part of a cycle. Nodes that are part of cycles or lead to cycles are marked unsafe.
• Nodes that eventually lead to terminal nodes or other safe nodes are marked safe.

We use a visited array with three states:

• 0: The node has not been visited yet.
• 1: The node is currently being visited (i.e., in the recursion stack).
• 2: The node has been fully processed and is safe.

Steps:

1. Perform DFS for each node.
2. Use the visited states to mark safe/unsafe nodes.
3. Collect all the nodes that are safe.

Let's implement this solution in PHP: 802. Find Eventual Safe States

<?php
/**
 * @param Integer[][] $graph
 * @return Integer[]
 */
function eventualSafeNodes($graph) {
    $n = count($graph);
    $visited = array_fill(0, $n, 0); // 0: unvisited, 1: visiting, 2: safe

    // Check every node for safety
    $safeNodes = [];
    for ($i = 0; $i < $n; $i++) {
        if (dfs($i, $graph, $visited) == 2) {
            $safeNodes[] = $i;
        }
    }

    return $safeNodes;
}

/**
 * DFS helper function
 *
 * @param $node
 * @param $graph
 * @param $visited
 * @return int|mixed
 */
function dfs($node, $graph, &$visited) {
    if ($visited[$node] != 0) {
        return $visited[$node]; // Return the state (safe or unsafe)
    }

    $visited[$node] = 1; // Mark the node as visiting
    foreach ($graph[$node] as $neighbor) {
        // If the neighbor leads to an unsafe node, current node is unsafe
        if (dfs($neighbor, $graph, $visited) == 1) {
            $visited[$node] = 1;
            return 1;
        }
    }

    $visited[$node] = 2; // Mark the node as safe
    return 2;
}

// Example usage:
$graph1 = [[1,2],[2,3],[5],[0],[5],[],[]];
$graph2 = [[1,2,3,4],[1,2],[3,4],[0,4],[]];

print_r(eventualSafeNodes($graph1)) . "\n"; // Output: [2,4,5,6]
print_r(eventualSafeNodes($graph2)) . "\n"; // Output: [4]
?>

Explanation:

1. DFS Function:

   • The dfs function performs a depth-first search on the node, marking it as "visiting" (1) when it starts and "safe" (2) when all its neighbors are safe.
   • If any of its neighbors leads to a cycle (indicated by dfs($neighbor) == 1), the node is marked unsafe (1).
   • If all neighbors lead to terminal nodes or safe nodes, it is marked as safe (2).

2. Main Function:

   • We iterate through all the nodes and use DFS to check whether each node is safe or not.
   • All safe nodes are collected in the $safeNodes array and returned.

Example Walkthrough:

Example 1:

$graph = [[1,2],[2,3],[5],[0],[5],[],[]];
print_r(eventualSafeNodes($graph));

• In this example, nodes 5 and 6 are terminal nodes (no outgoing edges).
• Node 4 leads to node 5, so it is also safe.
• Node 2 leads to node 5, so it is safe.
• Nodes 1 and 0 eventually lead to a cycle or unsafe nodes, so they are not safe.

Output:

[2, 4, 5, 6]

Example 2:

$graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]];
print_r(eventualSafeNodes($graph));

• In this example, only node 4 is a terminal node, and all paths starting from node 4 lead to node 4.
• All other nodes eventually lead to cycles or unsafe nodes.

Output:

[4]

Time and Space Complexity:

• Time Complexity: O(n + e), where n is the number of nodes and e is the number of edges. We visit each node once and process each edge once.
• Space Complexity: O(n) for the visited array and recursion stack.

This solution efficiently determines the safe nodes using DFS, ensuring that the problem constraints are met.

[basharul-siddike]

Thanks for solving the problem of "Find Eventual Safe States"

[mah-shamim]

Thanks