Problem Description

You are given a directed graph with n nodes labeled from 0 to n - 1. The graph is represented as a 2D array called graph, where graph[i] contains a list of all nodes that node i has edges pointing to.

A terminal node is defined as a node with no outgoing edges (its adjacency list is empty).

A safe node is defined as a node where every possible path starting from it will eventually reach a terminal node. This means no matter which edges you follow from a safe node, you will always end up at a terminal node without getting stuck in a cycle.

Your task is to find all the safe nodes in the graph and return them as a sorted list in ascending order.

For example, if node i has edges to nodes [j, k], then for node i to be safe, both paths through j and k must eventually lead to terminal nodes. If any path from node i could lead to a cycle or infinite loop, then node i is not safe.

The solution uses a reverse graph approach with topological sorting. It builds a reverse graph where edges point in the opposite direction, then uses the out-degree (which becomes in-degree in the reverse graph) to identify safe nodes. Starting from terminal nodes (which have out-degree 0), it works backwards to find all nodes that can only reach terminal nodes.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly states we have a directed graph with n nodes and edges represented by the adjacency list graph[i].

Is it a tree?

• No: The graph can have cycles and multiple paths between nodes. A tree would have no cycles and exactly one path between any two nodes.

Is the problem related to directed acyclic graphs?

• Yes: While the original graph may have cycles, the problem is essentially about identifying nodes that don't lead to cycles. We're looking for nodes that only lead to terminal nodes (no cycles). The solution approach treats this as a DAG problem by reversing the graph and finding nodes that can reach terminal nodes.

Topological Sort

• Yes: The flowchart leads us to Topological Sort, which is indeed used in the solution. The algorithm uses a modified topological sort on the reversed graph to identify safe nodes.

Conclusion: The flowchart correctly guides us to use Topological Sort for this problem. While DFS could also solve this problem (by detecting cycles), the given solution cleverly uses topological sorting on a reversed graph. It starts from terminal nodes (nodes with out-degree 0) and works backwards to find all nodes that only lead to these terminal nodes, effectively identifying all safe nodes.

Intuition

The key insight is to think about this problem in reverse. Instead of checking if every path from a node leads to a terminal node, we can ask: "Which nodes can only be reached from terminal nodes?"

Consider that a terminal node is trivially safe - it has no outgoing edges, so all paths from it (none) lead to terminal nodes. Now, if a node only points to terminal nodes, it must also be safe. We can extend this reasoning: if a node only points to safe nodes, then it must be safe too.

This suggests working backwards from terminal nodes. However, in the original graph, it's hard to work backwards because we'd need to know which nodes point TO a given node. This is where the reverse graph comes in - by reversing all edges, we can easily track dependencies.

In the reversed graph:

• Terminal nodes in the original graph have in-degree 0 in the reversed graph
• A node is safe if all nodes it depends on (points to in original graph) are safe

This naturally leads to a topological sort approach:

1. Start with nodes that have out-degree 0 (terminal nodes)
2. These are definitely safe
3. For each safe node we find, we can potentially make other nodes safe
4. A node becomes safe when all its outgoing edges lead to safe nodes (when its out-degree becomes 0 after removing edges to safe nodes)

The brilliance of this approach is that it avoids cycle detection entirely. Nodes involved in cycles will never have their out-degree reduced to 0, so they naturally get filtered out. Only nodes that can reach terminal nodes without going through cycles will eventually have their out-degree become 0.

Learn more about Depth-First Search, Breadth-First Search, Graph and Topological Sort patterns.

Solution Approach

The implementation uses a reverse graph with topological sorting to identify safe nodes. Here's how the solution works step by step:

1. Build the Reverse Graph and Track Out-degrees

rg = defaultdict(list)  # reverse graph
indeg = [0] * len(graph)  # actually stores out-degree of original graph

• rg[j] stores all nodes that point to node j in the original graph
• indeg[i] stores the out-degree of node i (number of outgoing edges)

2. Construct Reverse Graph

for i, vs in enumerate(graph):
    for j in vs:
        rg[j].append(i)  # if i->j in original, then j->i in reverse
    indeg[i] = len(vs)  # count outgoing edges

For each edge i → j in the original graph, we add edge j → i in the reverse graph.

3. Initialize Queue with Terminal Nodes

q = deque([i for i, v in enumerate(indeg) if v == 0])

Terminal nodes have out-degree 0, so we start with them as they are guaranteed to be safe.

4. Process Nodes in Topological Order

while q:
    i = q.popleft()
    for j in rg[i]:
        indeg[j] -= 1
        if indeg[j] == 0:
            q.append(j)

• When we process a safe node i, we look at all nodes j that point to i in the original graph
• We decrement the out-degree of j because one of its outgoing edges (to node i) is confirmed to lead to a safe node
• If all of j's outgoing edges lead to safe nodes (indeg[j] == 0), then j is also safe

5. Collect Results

return [i for i, v in enumerate(indeg) if v == 0]

After processing, any node with out-degree 0 is safe. Nodes in cycles or leading to cycles will never have their out-degree reduced to 0.

Time Complexity: O(V + E) where V is the number of nodes and E is the number of edges Space Complexity: O(V + E) for storing the reverse graph

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Example Graph:

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

This represents:

• Node 0 → [1, 2]
• Node 1 → [2, 3]
• Node 2 → [5]
• Node 3 → [0]
• Node 4 → [5]
• Node 5 → []
• Node 6 → []

Step 1: Build Reverse Graph and Track Out-degrees

First, we create the reverse graph and count out-degrees:

• Original edges: 0→1, 0→2, 1→2, 1→3, 2→5, 3→0, 4→5
• Reverse graph:
  • rg[0] = [3] (3 points to 0)
  • rg[1] = [0] (0 points to 1)
  • rg[2] = [0, 1] (0 and 1 point to 2)
  • rg[3] = [1] (1 points to 3)
  • rg[5] = [2, 4] (2 and 4 point to 5)
  • rg[6] = [] (nothing points to 6)
• Out-degrees: indeg = [2, 2, 1, 1, 1, 0, 0]

Step 2: Initialize Queue with Terminal Nodes

Terminal nodes have out-degree 0:

• Queue = [5, 6] (nodes 5 and 6 have no outgoing edges)

Step 3: Process Nodes in Topological Order

Process node 5:

• Look at rg[5] = [2, 4]
• Decrement indeg[2]: 1 → 0 (node 2 now safe!)
• Decrement indeg[4]: 1 → 0 (node 4 now safe!)
• Add nodes 2 and 4 to queue
• Queue = [6, 2, 4]

Process node 6:

• Look at rg[6] = [] (nothing to process)
• Queue = [2, 4]

Process node 2:

• Look at rg[2] = [0, 1]
• Decrement indeg[0]: 2 → 1
• Decrement indeg[1]: 2 → 1
• Neither reaches 0, so don't add to queue
• Queue = [4]

Process node 4:

• Look at rg[4] = [] (nothing to process)
• Queue = [] (empty)

Step 4: Identify Safe Nodes

After processing, check which nodes have out-degree 0:

• indeg = [1, 1, 0, 1, 0, 0, 0]
• Safe nodes: [2, 4, 5, 6]

Why This Works:

• Nodes 5 and 6 are terminal nodes (trivially safe)
• Node 2 only points to node 5 (a terminal node), so it's safe
• Node 4 only points to node 5 (a terminal node), so it's safe
• Nodes 0, 1, and 3 form a cycle: 0→1→3→0
  • Their out-degrees never reach 0 because they depend on each other
  • They are correctly identified as unsafe

The algorithm efficiently identifies all safe nodes without explicitly detecting cycles. Nodes in cycles naturally get filtered out because their dependencies can never be fully resolved.

Solution Implementation

Time and Space Complexity

Time Complexity: O(V + E) where V is the number of nodes and E is the total number of edges in the graph.

• Building the reverse graph requires iterating through all nodes and their edges: O(V + E)
• Initializing the indegree array takes O(V) time
• Finding initial nodes with indegree 0 requires O(V) time
• The BFS/topological sort processes each node at most once and each edge at most once: O(V + E)
• The final list comprehension to collect safe nodes takes O(V) time
• Overall: O(V + E) + O(V) + O(V) + O(V + E) + O(V) = O(V + E)

Space Complexity: O(V + E)

• The reverse graph rg stores all edges in reversed direction: O(E) space
• The indeg array stores the out-degree for each node: O(V) space
• The queue q can contain at most V nodes: O(V) space
• The output list contains at most V nodes: O(V) space
• Overall: O(E) + O(V) + O(V) + O(V) = O(V + E)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Out-degree Tracking

Pitfall: A common mistake is thinking that indeg or out_degree represents the in-degree of nodes in the reverse graph, when it actually tracks the out-degree of nodes in the original graph.

Why it happens: The variable naming can be confusing since we're building a reverse graph but tracking original out-degrees.

Incorrect approach:

# Wrong: Trying to track in-degrees of reverse graph
indeg = [0] * len(graph)
for node, neighbors in enumerate(graph):
    for neighbor in neighbors:
        indeg[node] += 1  # This is wrong!

Correct approach:

# Right: Track out-degrees of original graph
out_degree = [0] * len(graph)
for node, neighbors in enumerate(graph):
    out_degree[node] = len(neighbors)  # Count outgoing edges in original

2. Forgetting to Handle Self-loops Properly

Pitfall: Not recognizing that nodes with self-loops can never be safe nodes, but the algorithm handles this automatically.

Example scenario: If node 2 has an edge to itself graph[2] = [2, 3], some might think special handling is needed.

Why the algorithm works: A node with a self-loop will never have its out-degree reduced to 0 because it creates a cycle. The self-loop means the node will always have at least one outgoing edge that doesn't lead to a terminal node.

3. Attempting to Use Standard DFS Without Proper Cycle Detection

Pitfall: Trying to solve this with a simple DFS that doesn't properly track visited states.

Incorrect approach:

def isSafe(node, visited):
    if not graph[node]:  # terminal node
        return True
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor in visited or not isSafe(neighbor, visited):
            return False
    return True

Problem: This doesn't properly handle the case where different paths from a node might revisit the same nodes without forming a cycle.

Better DFS approach (if not using topological sort):

def isSafe(node, color):
    if color[node] != 0:  # Already processed
        return color[node] == 2
  
    color[node] = 1  # Mark as being processed (gray)
    for neighbor in graph[node]:
        if not isSafe(neighbor, color):
            return False
  
    color[node] = 2  # Mark as safe (black)
    return True

# Use three colors: 0 (white/unvisited), 1 (gray/processing), 2 (black/safe)
color = [0] * len(graph)
return [i for i in range(len(graph)) if isSafe(i, color)]

4. Not Recognizing That Order Matters in the Result

Pitfall: Forgetting to return the safe nodes in ascending order.

Wrong:

# If using a set to collect results
safe_nodes = set()
# ... processing ...
return list(safe_nodes)  # Order not guaranteed!

Correct:

# The enumerate approach naturally maintains order
return [node for node, degree in enumerate(out_degree) if degree == 0]

5. Incorrectly Initializing the Queue

Pitfall: Adding nodes to the initial queue based on in-degree in the reverse graph rather than out-degree in the original graph.

Wrong:

# Counting in-degrees of reverse graph for initialization
indeg_reverse = [0] * len(graph)
for node, neighbors in enumerate(graph):
    for neighbor in neighbors:
        indeg_reverse[neighbor] += 1
queue = deque([i for i, v in enumerate(indeg_reverse) if v == 0])

Correct:

# Initialize with terminal nodes (out-degree 0 in original)
queue = deque([node for node, degree in enumerate(out_degree) if degree == 0])

These terminal nodes are the foundation of safety - they guarantee termination of any path, which is why we start our backward traversal from them.