{x}
blog image

Find Eventual Safe States

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:

Illustration of graph 
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].

Solution Explanation for 802. Find Eventual Safe States

This problem asks to find all the safe nodes in a directed graph. A safe node is defined as a node from which all paths eventually lead to a terminal node (a node with no outgoing edges). We can solve this using two main approaches: Topological Sort and Depth-First Search (DFS).

Approach 1: Topological Sort

This approach leverages the concept of topological sorting. We build a reverse graph, where edges point from the nodes a node points to back to the node itself. Then, we perform a topological sort on this reversed graph. Nodes with an in-degree of 0 in the reversed graph are terminal nodes or nodes reachable only from terminal nodes, hence they are safe. The algorithm proceeds as follows:

  1. Reverse Graph Construction: Create a reverse graph (rg) where rg[j] contains all nodes i such that there's an edge from i to j in the original graph.

  2. In-degree Calculation: Calculate the in-degree (indeg) for each node in the reversed graph. The in-degree represents the number of incoming edges to a node.

  3. Topological Sort: Use a queue to perform a topological sort. Start by adding nodes with an in-degree of 0 to the queue. These are our starting points (terminal nodes). Iteratively remove nodes from the queue, and for each node's neighbors in the reverse graph, decrement their in-degree. If a neighbor's in-degree becomes 0, add it to the queue.

  4. Safe Nodes Identification: After the topological sort, nodes with an in-degree of 0 are the safe nodes, because they are reachable from terminal nodes and only terminal nodes.

Time Complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is due to the linear time complexity of building the reverse graph, calculating in-degrees, and performing the topological sort.

Space Complexity: O(V + E) to store the reverse graph, in-degree array, and queue.

Approach 2: Depth-First Search (DFS)

This approach uses DFS with a color-coding system to detect cycles. The states are represented by colors:

  • 0: Unvisited
  • 1: Visiting (currently in the DFS recursion)
  • 2: Visited (DFS recursion completed)

The algorithm operates as follows:

  1. DFS function: Recursively explores the graph. If a node is marked as 1 (visiting), a cycle is detected, and the node is not safe. If a node is marked as 0, we mark it as 1, recursively explore its neighbors, and then mark it as 2 once all neighbors are processed.

  2. Safe Node Identification: Nodes that complete the DFS without encountering a cycle (marked as 2) are safe.

Time Complexity: O(V + E) The DFS visits each node and edge at most once.

Space Complexity: O(V) for the color array and recursion stack.

Code Examples (Python)

Approach 1 (Topological Sort):

from collections import defaultdict, deque
 
class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        rg = defaultdict(list)  # Reverse graph
        indeg = [0] * n         # In-degree array
 
        for i, neighbors in enumerate(graph):
            for neighbor in neighbors:
                rg[neighbor].append(i)
            indeg[i] = len(neighbors)
 
        q = deque([i for i, d in enumerate(indeg) if d == 0]) #nodes with no incoming edges
        while q:
            i = q.popleft()
            for j in rg[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return [i for i, d in enumerate(indeg) if d == 0]

Approach 2 (DFS):

class Solution:
    def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
        n = len(graph)
        color = [0] * n  # 0: unvisited, 1: visiting, 2: visited
 
        def dfs(node):
            if color[node] == 1: return False  # Cycle detected
            if color[node] == 2: return True   # Already visited
 
            color[node] = 1  # Mark as visiting
            for neighbor in graph[node]:
                if not dfs(neighbor):
                    return False
            color[node] = 2  # Mark as visited
            return True
 
        return [i for i in range(n) if dfs(i)]

Both approaches provide efficient solutions to this problem with linear time and space complexity. The choice between them might depend on personal preference or specific constraints of the problem context. The DFS approach might be slightly easier to understand intuitively for those less familiar with topological sort.