802. Find Eventual Safe States


Problem Description

In this problem, we are given a directed graph with n nodes labeled from 0 to n-1. The graph is defined by a 2-dimensional array graph where graph[i] contains a list of nodes that have directed edges from node i. If a node doesn't have any outgoing edges, we label it as a terminal node. Our task is to find all the safe nodes in this graph. A safe node is one from which every possible path leads to a terminal node or to another safe node (which will eventually lead to a terminal node).

Our goal is to return an array of all the safe nodes in sorted ascending order.

Intuition

The concept of safe nodes can be thought of in terms of a topological sort—the nodes that can eventually reach terminal nodes without falling into a cycle are considered safe. We can represent each node with different states to help us in our search for safe nodes: unvisited (color 0), visiting (color 1), and safe (color 2).

The depth-first search (DFS) algorithm can help us perform this search. If we are visiting a node and encounter a node that is already being visited, this means we have a cycle, and hence, the starting node cannot be a safe node. On the contrary, if all paths from a node lead to nodes that are already known to be safe or terminal, the node in question is also safe.

We make use of a coloring system to mark the nodes:

  • Color 0: The node has not been visited yet.
  • Color 1: The node is currently being visited (we're in the process of exploring its edges).
  • Color 2: The node and all its children can safely lead to a terminal node.

We start our DFS with the unvisited nodes and explore their children. If during the exploration, we encounter a node that is currently being visited (color 1), this means there is a cycle, and we return False, marking the node as unsafe. We continue this process for all nodes, and those that end up marked as color 2 (safe), are added to our list of safe nodes.

This approach ensures that we are only considering nodes that lead to terminal nodes as safe, effectively implementing a topological sort, which is suitable for such dependency-based problems.

Solution Approach

The solution approach is centered on using the concepts of Depth-First Search (DFS) and coloring to determine which nodes are safe in the graph.

The key part of the implementation is the dfs function, which is recursive and performs the following steps:

  1. Check if the current node i has already been visited:
    • If so, return whether it's a safe node (color[i] == 2).
  2. Mark the node as currently being visited (color it with 1).
  3. Iterate through all the adjacent nodes (those found in graph[i]):
    • For each adjacent node, call the dfs function on it. If the dfs on any child returns False, marking it as part of a cycle or path to an unsafe node, the current node i cannot be a safe node, so return False.
  4. If all adjacent nodes are safe or lead to safe nodes, mark the current node i as safe (color it with 2) and return True.

The driver code does the following:

  • Initializes an array color with n elements as 0, to store the state (unvisited, visiting, or safe) of each node.
  • It then iterates over each node and applies the dfs function. If the dfs function returns True, it indicates the node is safe, and it's added to the final list of safe nodes.
  • The list of safe nodes is then returned, which are the nodes from which every path leads to a terminal node or eventually reaches another safe node.

This approach is efficient as it marks nodes that are part of cycles as unsafe early on through the depth-first search and avoids reprocessing nodes that have already been determined to be safe or unsafe. This minimizes the exploration we need to do when determining the safety of subsequent nodes.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a simple directed graph with four nodes (0 to 3) defined by the 2-dimensional array graph:

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

Here, we have edges from node 0 to nodes 1 and 2, from node 1 to node 2, and from node 2 to node 3. Node 3 doesn't have any outgoing edges, so it's a terminal node.

We apply our DFS-based solution approach to identify safe nodes.

  1. Start with node 0, which is unvisited. We mark it as visiting (color it with 1).
  2. We see that node 0 has two adjacent nodes: node 1 and node 2. We explore node 1 first:
    • Node 1 is unvisited; mark it as visiting (color 1).
    • Node 1 has one adjacent node, node 2. We explore node 2:
      • Node 2 is unvisited; mark it as visiting (color 1).
      • Node 2 has one adjacent node, node 3. We explore node 3:
        • Node 3 is unvisited and has no outgoing edges, so it's a terminal node. Mark it as safe (color 2).
      • Since node 3 is safe, we mark node 2 as safe (color 2) and return True.
    • Since node 2 is safe, we mark node 1 as safe (color 2) and return True.
  3. Then we resume exploring the adjacent nodes of node 0 and move on to node 2.
    • Node 2 is already marked safe (color 2), so we return True.
  4. All paths from node 0 lead to safe nodes, so we mark node 0 as safe (color 2).

Since we've visited all nodes and no cycles were detected, and all nodes lead to a terminal node, all nodes (0, 1, 2, 3) are marked as safe.

In the end, the driver code collects all nodes colored as 2, sorts them (which is not necessary in this case, as the array is already sorted), and returns the list of safe nodes: [0, 1, 2, 3].

Python Solution

1from typing import List
2
3class Solution:
4    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
5        # Helper function to perform a depth-first-search (dfs) 
6        # to determine if a node leads to a cycle (not safe) or not.
7        def dfs(node_index):
8            # If the node is already visited, return True if it is safe (color 2)
9            if node_colors[node_index]:
10                return node_colors[node_index] == 2
11            # Mark this node as visited (color 1)
12            node_colors[node_index] = 1
13            # Traverse all connected nodes to see if they lead to a cycle
14            for next_node_index in graph[node_index]:
15                # If a connected node is not safe, then this node is also not safe
16                if not dfs(next_node_index):
17                    return False
18            # If all connected nodes are safe, mark this node as safe (color 2)
19            node_colors[node_index] = 2
20            return True
21
22        # Get the number of nodes in the graph
23        total_nodes = len(graph)
24        # Initialize a list to store the status of the nodes
25        # Color 0 means unvisited, 1 means visiting, 2 means safe
26        node_colors = [0] * total_nodes
27        # Use list comprehension to gather all nodes that are safe after DFS
28        # These are the eventual safe nodes that do not lead to any cycles
29        safe_nodes = [node_index for node_index in range(total_nodes) if dfs(node_index)]
30        return safe_nodes
31

Java Solution

1class Solution {
2    private int[] nodeColors;
3    private int[][] graph;
4
5    // Method to determine all the eventual safe nodes in a graph
6    public List<Integer> eventualSafeNodes(int[][] graph) {
7        int n = graph.length;
8        nodeColors = new int[n]; // Initialize array to store the state of each node
9        this.graph = graph; // Assign graph to class variable for easy access
10        List<Integer> safeNodes = new ArrayList<>(); // List to store eventual safe nodes
11      
12        // Iterate over each node to determine if it's a safe node
13        for (int i = 0; i < n; ++i) {
14            if (isNodeSafe(i)) { // If the current node is safe, add it to the list
15                safeNodes.add(i);
16            }
17        }
18        return safeNodes; // Return the final list of safe nodes
19    }
20
21    // Helper method - Conducts a depth-first search to determine if a node is safe.
22    // A node is considered safe if all its possible paths lead to a terminal node.
23    private boolean isNodeSafe(int node) {
24        if (nodeColors[node] > 0) { // If the node is already visited, return its state
25            return nodeColors[node] == 2; // Return true if the node leads to a terminal node, i.e., is safe (color coded as 2)
26        }
27        nodeColors[node] = 1; // Mark the node as visited (color coded as 1)
28      
29        // Explore all connected nodes recursively
30        for (int neighbor : graph[node]) {
31            if (!isNodeSafe(neighbor)) { // If any connected node is not safe, then this node is not safe either
32                return false;
33            }
34        }
35      
36        nodeColors[node] = 2; // Since all connected nodes are safe, mark this node as safe (color coded as 2)
37        return true; // Return true indicating the node is safe
38    }
39}
40

C++ Solution

1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    vector<int> colors; // Color array to mark the states of nodes: 0 = unvisited, 1 = visiting, 2 = safe
7
8    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
9        int n = graph.size();
10        colors.assign(n, 0); // Initialize all nodes as unvisited
11        vector<int> safeNodes; // List to hold the eventual safe nodes
12
13        // Check each node to see if it's eventually safe
14        for (int i = 0; i < n; ++i) {
15            if (dfs(i, graph)) {
16                safeNodes.push_back(i); // If it is safe, add it to the list
17            }
18        }
19
20        return safeNodes; // Return the list of safe nodes
21    }
22
23    // Depth-first search to determine if a node is safe
24    bool dfs(int nodeIndex, vector<vector<int>>& graph) {
25        if (colors[nodeIndex]) {
26            // If the node has been visited already, return true only if it's marked as safe
27            return colors[nodeIndex] == 2;
28        }
29
30        colors[nodeIndex] = 1; // Mark the node as visiting
31        for (int neighbor : graph[nodeIndex]) {
32            // Explore all the neighbors of the current node
33            if (!dfs(neighbor, graph)) {
34                // If any neighbor is not safe, the current node is not safe either
35                return false;
36            }
37        }
38
39        colors[nodeIndex] = 2; // Mark the node as safe
40        return true; // Return true as the node is safe
41    }
42};
43

Typescript Solution

1// Function to determine the eventual safe nodes in a graph
2// @param graph - The adjacency list representation of a directed graph
3// @returns An array of indices representing eventual safe nodes
4const eventualSafeNodes = (graph: number[][]): number[] => {
5    const n: number = graph.length; // Number of nodes in the graph
6    const color: number[] = new Array(n).fill(0); // Array to mark the state of each node: 0 = unvisited, 1 = visiting, 2 = safe
7
8    // Depth-first search function to determine if a node leads to a cycle or not
9    // @param nodeIndex - The current node index being visited
10    // @returns A boolean indicating if the node is safe (does not lead to a cycle)
11    const dfs = (nodeIndex: number): boolean => {
12        if (color[nodeIndex]) {
13            // If the node has been visited, return true if it's marked as safe, false otherwise
14            return color[nodeIndex] === 2;
15        }
16        color[nodeIndex] = 1; // Mark the node as visiting
17        for (const neighbor of graph[nodeIndex]) {
18            // Visit all neighbors to see if any lead to a cycle
19            if (!dfs(neighbor)) {
20                // If any neighbor is not safe, the current node is not safe either
21                return false;
22            }
23        }
24        color[nodeIndex] = 2; // Mark the node as safe since no cycles were found from it
25        return true; // The node is safe
26    };
27
28    let ans: number[] = []; // Initialize an array to keep track of safe nodes
29    for (let i = 0; i < n; ++i) {
30        // Iterate over each node in the graph
31        if (dfs(i)) {
32            // If the node is safe, add it to the result
33            ans.push(i);
34        }
35    }
36    return ans; // Return the list of safe nodes
37};
38

Time and Space Complexity

Time Complexity

The time complexity is O(N + E), where N is the number of nodes and E is the number of edges in the graph. This is because each node is processed exactly once, and we perform a Depth-First Search (DFS) that in total will explore each edge once. When a node is painted grey (color[i] = 1), it represents that the node is being processed. If it is painted black (color[i] = 2), the node and all nodes leading from it are safe. The DFS will terminate early if a loop is found (thus encountering a grey node during DFS), ensuring each edge is only fully explored once in the case of a safe node.

Space Complexity

The space complexity is O(N). This is due to the color array, which keeps track of the state of each node, using space proportional to the number of nodes N. Additionally, the system stack space used by the recursive DFS calls must also be considered; in the worst case, where the graph is a single long path, the recursion depth could potentially be N, adding to the space complexity. However, since space used by the call stack during recursion and the color array are both linear with respect to the number of nodes, the overall space complexity remains O(N).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫