Taro Logo

Find Eventual Safe States

Medium
Amazon logo
Amazon
Topics:
GraphsDynamic Programming

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.

Could you write a function to identify and return all safe nodes in the graph, sorted in ascending order? How would you approach this problem, considering efficiency and edge cases?

Solution


Safe Nodes in a Directed Graph

Problem Description

Given a directed graph of n nodes labeled from 0 to n - 1, where the graph is represented by a 0-indexed 2D integer array graph, where graph[i] is an array of nodes adjacent to node i, indicating an edge from node i to each node in graph[i]. A node is a terminal node if it has 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). The task is to return a sorted array of all the safe nodes in the graph.

Example

Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]

Naive Approach (Brute Force)

The brute force approach involves performing a Depth-First Search (DFS) from each node to check if all paths lead to a terminal node. For each node, explore all possible paths. If a cycle is detected, then the node is not safe. If all paths end in terminal nodes, then the node is safe.

Algorithm

  1. For each node i from 0 to n - 1:
  2. Perform a DFS starting from node i.
  3. During the DFS, maintain a visited set to detect cycles.
  4. If a cycle is detected, the node is not safe.
  5. If all paths from node i lead to terminal nodes without cycles, then node i is safe.

Code (Python)

def is_safe_node_brute_force(graph, node, visited, path):
    visited[node] = True
    path[node] = True

    for neighbor in graph[node]:
        if path[neighbor]:
            return False  # Cycle detected
        if not visited[neighbor]:
            if not is_safe_node_brute_force(graph, neighbor, visited, path):
                return False

    path[node] = False  # Backtrack: remove node from current path
    return True

def safe_nodes_brute_force(graph):
    n = len(graph)
    safe_nodes = []
    for i in range(n):
        visited = [False] * n
        path = [False] * n
        if is_safe_node_brute_force(graph, i, visited, path):
            safe_nodes.append(i)
    return sorted(safe_nodes)

Time Complexity

O(n * (V + E)), where n is the number of nodes, V is the number of vertices, and E is the number of edges. For each node, we may have to traverse the entire graph.

Space Complexity

O(n) due to the visited and path arrays and the recursion stack in the worst case.

Optimal Approach (Using Topological Sort / Reverse Graph)

The optimal approach involves reversing the graph and using topological sorting. A node is safe if all the nodes that lead to it are safe. By reversing the graph, we can identify terminal nodes in the reversed graph, which were nodes that other nodes led into.

Algorithm

  1. Reverse the graph: create a new graph where edges are reversed.
  2. Find nodes with zero in-degree in the reversed graph (these are equivalent to terminal nodes in the original graph).
  3. Perform a topological sort (using Kahn's algorithm or DFS) on the reversed graph.
  4. The nodes visited during the topological sort are the safe nodes.

Code (Python)

from collections import deque

def safe_nodes_optimal(graph):
    n = len(graph)
    reversed_graph = [[] for _ in range(n)]
    in_degree = [0] * n

    for i in range(n):
        for neighbor in graph[i]:
            reversed_graph[neighbor].append(i)
            in_degree[i] += 1

    queue = deque([i for i in range(n) if in_degree[i] == 0])
    safe_nodes = []

    while queue:
        node = queue.popleft()
        safe_nodes.append(node)

        for neighbor in reversed_graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return sorted(safe_nodes)

Time Complexity

O(V + E), where V is the number of vertices and E is the number of edges, because reversing the graph and Kahn's algorithm both take O(V+E) time.

Space Complexity

O(V + E) to store the reversed graph, in-degree array, and the queue.

Edge Cases

  • Empty Graph: If the graph is empty (n = 0), return an empty array.
  • Self-Loops: The graph may contain self-loops; the algorithm should handle these correctly.
  • Disconnected Graph: The graph may be disconnected; the algorithm should still identify all safe nodes.
  • Single Node Graph: If the graph has only one node, check if it's a terminal node.