algoadvance

You are given a directed graph of n nodes represented by an adjacency list, where graph[i] is a list of nodes that node i has edges to. A node is considered safe if and only if every possible path starting from that node leads to a terminal node (i.e., a node that has no outgoing edges). Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.

Example:

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

Explanation:
Node 5 and 6 are terminal nodes.
Node 2 and 4 lead to terminal nodes.

Clarifying Questions

  1. Q: Can the graph contain cycles?
    • A: Yes, the graph can contain cycles.
  2. Q: What is the range of the number of nodes n?
    • A: Typically constraints for such problems are 1 <= n <= 10^4.
  3. Q: Are there any duplicate edges in the graph?
    • A: No, each edge is unique.
  4. Q: Can the graph be disconnected?
    • A: Yes, the graph can be disconnected.

Strategy

To identify eventual safe nodes:

  1. Reverse Graph: Construct the reverse graph where each edge (u, v) in the original graph becomes (v, u).
  2. Track Outbound Edges: Track the number of outgoing edges for each node in the original graph.
  3. Queue Initialization: Initialize a queue with all terminal nodes (nodes with zero outgoing edges in the original graph).
  4. Process the Queue:
    • Remove nodes from the queue one by one.
    • Reduce the outgoing edge count for each predecessor of the current node (according to the reverse graph).
    • If any predecessor now has zero outgoing edges, add it to the queue.
  5. Collect Safe Nodes: Nodes that have been processed (those that have no remaining edges) are the safe nodes.
  6. Sort: Sort the safe nodes before returning.

Code

from collections import deque, defaultdict

def eventualSafeNodes(graph):
    n = len(graph)
    
    # Reverse graph adjacency list
    reverse_graph = defaultdict(list)
    
    # Count of outbound edges for each node
    outbound_count = [0] * n
    
    for node, neighbors in enumerate(graph):
        outbound_count[node] = len(neighbors)
        for neighbor in neighbors:
            reverse_graph[neighbor].append(node)
    
    # Queue initialization with terminal nodes (nodes with 0 outbound edges)
    queue = deque([node for node, count in enumerate(outbound_count) if count == 0])
    safe_nodes = []
    
    while queue:
        current_node = queue.popleft()
        safe_nodes.append(current_node)  # Safe node found
        
        for predecessor in reverse_graph[current_node]:
            outbound_count[predecessor] -= 1  # Reduce outbound edges count
            if outbound_count[predecessor] == 0:
                queue.append(predecessor)  # Add new terminal node to the queue
    
    return sorted(safe_nodes)

# Test the function with an example input
graph = [[1,2],[2,3],[5],[0],[5],[],[]]
print(eventualSafeNodes(graph))  # Output: [2, 4, 5, 6]

Time Complexity

Total Time Complexity: O(V + E + V log V) which simplifies to O(V log V + E).

Try our interview co-pilot at AlgoAdvance.com