Find Eventual Safe States

▶

Steps

setup

Initialize variables and reverse graph structure

Create an empty reverse graph with the same number of nodes as the input graph and initialize the in-degree array to zero for all nodes.

💡 Setting up the reverse graph and in-degree array prepares the data structures needed to track node dependencies in the reversed graph.

Line:

n = len(graph)
reverse_graph = [[] for _ in range(n)]
in_degree = [0] * n

💡 The reverse graph will store edges reversed from the original graph, and in-degree will count outgoing edges in the original graph.

setup

Build reverse graph and compute in-degree for node 0

For node 0, add edges in the reverse graph from its neighbors 1 and 2 back to 0. Set in-degree of node 0 to the number of its neighbors (2).

💡 Reversing edges means predecessors point to current node; in-degree counts outgoing edges in original graph.

Line:

for v in graph[u]:
    reverse_graph[v].append(u)
in_degree[u] = len(graph[u])

💡 Node 0 has two outgoing edges, so in-degree[0] = 2; reverse edges added from 1->0 and 2->0.

setup

Build reverse graph and compute in-degree for node 1

For node 1, add reverse edges from neighbors 2 and 3 back to 1. Set in-degree of node 1 to 2.

💡 Continuing to build reverse graph and track out-degree counts for each node.

Line:

for v in graph[u]:
    reverse_graph[v].append(u)
in_degree[u] = len(graph[u])

💡 Node 1 has two outgoing edges, so in-degree[1] = 2; reverse edges added from 2->1 and 3->1.

setup

Build reverse graph and compute in-degree for node 2

For node 2, add reverse edge from neighbor 5 back to 2. Set in-degree of node 2 to 1.

💡 Each node's out-degree is counted and reverse edges are added to track predecessors.

Line:

for v in graph[u]:
    reverse_graph[v].append(u)
in_degree[u] = len(graph[u])

💡 Node 2 has one outgoing edge, so in-degree[2] = 1; reverse edge added from 5->2.

setup

Build reverse graph and compute in-degree for node 3

For node 3, add reverse edge from neighbor 0 back to 3. Set in-degree of node 3 to 1.

💡 Reverse edges track which nodes lead to the current node in the original graph.

Line:

for v in graph[u]:
    reverse_graph[v].append(u)
in_degree[u] = len(graph[u])

💡 Node 3 has one outgoing edge, so in-degree[3] = 1; reverse edge added from 0->3.

setup

Build reverse graph and compute in-degree for node 4

For node 4, add reverse edge from neighbor 5 back to 4. Set in-degree of node 4 to 1.

💡 This step continues building the reversed graph and tracking out-degree counts.

Line:

for v in graph[u]:
    reverse_graph[v].append(u)
in_degree[u] = len(graph[u])

💡 Node 4 has one outgoing edge, so in-degree[4] = 1; reverse edge added from 5->4.

setup

Build reverse graph and compute in-degree for node 5

Node 5 has no outgoing edges, so in-degree is 0 and no reverse edges are added.

💡 Terminal nodes have zero out-degree and thus zero in-degree in the reversed graph.

Line:

in_degree[u] = len(graph[u])

💡 Node 5 is a terminal node and will be added to the initial queue of safe nodes.

setup

Build reverse graph and compute in-degree for node 6

Node 6 has no outgoing edges, so in-degree is 0 and no reverse edges are added.

💡 Another terminal node identified by zero out-degree.

Line:

in_degree[u] = len(graph[u])

💡 Node 6 is terminal and will be added to the initial queue.

setup

Initialize queue with nodes having zero in-degree

Add nodes 5 and 6 to the queue because their in-degree is zero, indicating they are terminal nodes.

💡 Starting with terminal nodes allows the algorithm to propagate safety backwards through the graph.

Line:

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

💡 Nodes with zero in-degree in the reversed graph are safe starting points.

traverse

Process node 5 from queue

Dequeue node 5, mark it as done (safe), and add it to the safe list. Then, for each predecessor of 5 in the reverse graph (nodes 2 and 4), decrement their in-degree.

💡 Processing node 5 shows how safety propagates backward to its predecessors by reducing their in-degree.

Line:

node = queue.popleft()
safe.append(node)
for prev in reverse_graph[node]:
    in_degree[prev] -= 1
    if in_degree[prev] == 0:
        queue.append(prev)

💡 When a node's in-degree drops to zero, it means all its outgoing edges lead to safe nodes, so it is safe too.

traverse

Process node 6 from queue

Dequeue node 6, mark it as done (safe), and add it to the safe list. Node 6 has no predecessors, so no in-degree updates occur.

💡 Terminal nodes with no predecessors simply get marked safe and removed from the queue.

Line:

node = queue.popleft()
safe.append(node)
for prev in reverse_graph[node]:
    in_degree[prev] -= 1
    if in_degree[prev] == 0:
        queue.append(prev)

💡 Terminal nodes are safe by definition and help identify other safe nodes.

traverse

Process node 2 from queue

Dequeue node 2, mark it as done (safe), and add it to the safe list. For its predecessor 0 and 1, decrement in-degree. Node 0's in-degree becomes 1, node 1's becomes 1.

💡 Processing node 2 propagates safety backward, but predecessors are not yet safe as their in-degree is not zero.

Line:

node = queue.popleft()
safe.append(node)
for prev in reverse_graph[node]:
    in_degree[prev] -= 1
    if in_degree[prev] == 0:
        queue.append(prev)

💡 A node becomes safe only when all its outgoing edges lead to safe nodes, reflected by in-degree zero.

traverse

Process node 4 from queue

Dequeue node 4, mark it as done (safe), and add it to the safe list. For its predecessor 5, decrement in-degree (already zero). No new nodes added to queue.

💡 Node 4 is safe; its predecessor 5 is already safe, so no changes to in-degree or queue.

Line:

node = queue.popleft()
safe.append(node)
for prev in reverse_graph[node]:
    in_degree[prev] -= 1
    if in_degree[prev] == 0:
        queue.append(prev)

💡 Safe nodes can have safe predecessors already processed; no further action needed.

reconstruct

End of queue processing; sort safe nodes

All nodes with zero in-degree have been processed and marked safe. The safe list contains nodes 5, 6, 2, and 4. Sort this list to produce the final output.

💡 Sorting the safe nodes gives the final answer in ascending order.

Line:

return sorted(safe)

💡 Safe nodes are those that lead only to terminal or other safe nodes.

from typing import List
from collections import deque

def eventualSafeNodes(graph: List[List[int]]) -> List[int]:
    n = len(graph)  # STEP 1
    reverse_graph = [[] for _ in range(n)]  # STEP 1
    in_degree = [0] * n  # STEP 1

    for u in range(n):  # STEP 2-8
        for v in graph[u]:  # STEP 2-8
            reverse_graph[v].append(u)  # STEP 2-8
        in_degree[u] = len(graph[u])  # STEP 2-8

    queue = deque([i for i in range(n) if in_degree[i] == 0])  # STEP 9
    safe = []  # STEP 1

    while queue:  # STEP 10-13
        node = queue.popleft()  # STEP 10-13
        safe.append(node)  # STEP 10-13
        for prev in reverse_graph[node]:  # STEP 10-13
            in_degree[prev] -= 1  # STEP 10-13
            if in_degree[prev] == 0:  # STEP 10-13
                queue.append(prev)  # STEP 10-13

    return sorted(safe)  # STEP 14

if __name__ == '__main__':
    graph = [[1,2],[2,3],[5],[0],[5],[],[]]
    print(eventualSafeNodes(graph))

📊

Find Eventual Safe States - Watch the Algorithm Execute, Step by Step

Watching each step of Kahn's Algorithm applied to the reversed graph reveals how safe nodes are identified by progressively removing nodes that lead only to terminal or safe nodes.

Visiting: none

0

1

2

3

4

5

6

Visiting: 0

0

1

2

3

4

5

6

Visiting: 1

0

1

2

3

4

5

6

Visiting: 2

0

1

2

3

4

5

6

Visiting: 3

0

1

2

3

4

5

6

Visiting: 4

0

1

2

3

4

5

6

Visiting: 5

0

1

2

3

4

5

6

Visiting: 6

0

1

2

3

4

5

6

Visiting: none

0

1

2

3

4

5

6

Queue / Stack

56

Visiting: 5

Edge: 5 → 2

0

1

2

3

4

5

6

Queue / Stack

624

Visiting: 6

0

1

2

3

4

5

6

Queue / Stack

24

Visiting: 2

Edge: 2 → 0

0

1

2

3

4

5

6

Queue / Stack

4

Visiting: 4

0

1

2

3

4

5

6

Visiting: none

0

1

2

3

4

5

6

Key Takeaways

✓ Reversing the graph and using in-degree counts allows identification of safe nodes by starting from terminal nodes.

This insight is difficult to grasp from code alone because it requires understanding the reversed graph's role in safety propagation.

✓ Nodes become safe only when all their outgoing edges lead to safe nodes, reflected by their in-degree dropping to zero.

Visualizing in-degree decrement and queue updates clarifies how safety propagates backward through the graph.

✓ Terminal nodes are the initial safe nodes and serve as the base case for the algorithm's BFS traversal.

Seeing terminal nodes enqueued first helps concretely understand why they are inherently safe.

Practice

1. Consider the following buggy code snippet for topological sort positions. Which line contains the subtle bug that can cause incorrect matrix construction?

medium

A. Line where graph[u].append(v) is called

B. Line where queue is initialized with nodes of zero in-degree

C. Line where pos[node] is assigned idx

D. Line where in_degree[u] is incremented instead of in_degree[v]

Solution

1. Step 1: Identify how in-degree is updated

   In-degree should count incoming edges; incrementing in_degree[u] is incorrect because u is the source, not the target.

2. Step 2: Understand impact of bug

   Incorrect in-degree counts cause wrong zero in-degree nodes, breaking topological order and matrix correctness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct in-degree update is critical for cycle detection and ordering [OK]

Hint: In-degree counts incoming edges, not outgoing [OK]

Common Mistakes:

• Mixing source and target when updating in-degree
• Assuming graph edges are undirected

2. Consider the following buggy implementation of Kahn's Algorithm for course scheduling. Which line contains the subtle bug that can cause incorrect or infinite behavior?

medium

A. Line 6: graph[a].append(b) -- edge direction reversed

B. Line 7: in_degree[a] += 1 -- incorrect in-degree increment

C. Line 10: queue initialization -- wrong nodes enqueued

D. Line 15: in_degree[nei] -= 1 -- decrementing in-degree incorrectly

Solution

1. Step 1: Analyze edge construction

   Prerequisite pairs are (a, b) meaning b -> a edge; reversing to graph[a].append(b) flips direction.

2. Step 2: Consequences of reversed edges

   In-degree counts and BFS queue become invalid, causing wrong order or infinite loop.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct edge direction is critical for topological sort correctness [OK]

Hint: Check edge direction carefully when building graph [OK]

Common Mistakes:

• Reversing edges when building adjacency list
• Incrementing in-degree on wrong node
• Forgetting to decrement in-degree

3. Examine the following code snippet for the largest color value problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

from collections import defaultdict, deque

def largestPathValue(colors, edges):
    n = len(colors)
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    dp = [[0]*26 for _ in range(n)]
    queue = deque([i for i in range(n) if indegree[i] == 0])
    count = 0
    max_color_value = 0

    while queue:
        node = queue.popleft()
        count += 1
        c_index = ord(colors[node]) - ord('a')
        dp[node][c_index] += 1
        max_color_value = max(max_color_value, dp[node][c_index])

        for nei in graph[node]:
            for i in range(26):
                dp[nei][i] = max(dp[nei][i], dp[node][i])
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)

    if count != n:
        return -1  # cycle detected
    return max_color_value

medium

A. Line incrementing dp[node][c_index]

B. Line updating dp[nei][i] inside the nested loop

C. Line checking if count != n to detect cycles

D. Line initializing the queue with nodes having indegree zero

Solution

1. Step 1: Understand dp update logic

   dp[nei][i] should aggregate max counts from predecessors, but the code overwrites dp[nei][i] without adding the neighbor's own color count.

2. Step 2: Identify bug

   The bug is that dp[nei][i] = max(dp[nei][i], dp[node][i]) does not add the neighbor's own color count, causing undercounting.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Incorrect aggregation leads to wrong max color values [OK]

Hint: Check if dp updates correctly accumulate color counts [OK]

Common Mistakes:

• Not aggregating color counts from neighbors properly

4. Examine the following buggy code snippet for sequence reconstruction using DFS postorder topological sort. Which line contains the subtle bug that can cause incorrect results when seqs is missing some elements from org?

medium

A. Line 7: Missing check if all nodes in org appear in seqs

B. Line 12: Incorrect graph edge insertion logic

C. Line 18: Incorrect cycle detection marking

D. Line 27: Missing stack reversal before comparison

Solution

1. Step 1: Identify missing validation

   The code does not check if all elements in org appear in seqs, which can cause false positives.

2. Step 2: Confirm other lines are correct

   Graph construction, cycle detection, and stack reversal are implemented correctly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing node presence check leads to incorrect true when seqs incomplete [OK]

Hint: Always verify all org nodes appear in seqs [OK]

Common Mistakes:

• Ignoring node presence check
• Misplacing cycle detection flags

5. Suppose the alien dictionary problem is extended so that characters can appear multiple times in the same word and the order must reflect the first occurrence precedence only. Which modification to the topological sort approach correctly handles this variant without breaking correctness or efficiency?

hard

A. Modify graph construction to add edges for every differing character pair in all positions, not just first differing character

B. Use a brute force approach comparing all pairs of words and all character positions to build edges

C. Keep only the first differing character pair between adjacent words to add edges, ignoring subsequent differences

D. Ignore repeated characters and treat each character as unique node per occurrence

Solution

1. Step 1: Understand variant requirement

   Order depends only on first differing character between adjacent words, even if characters repeat later.

2. Step 2: Confirm correct approach

   Adding edges only for the first differing character pair preserves partial order and avoids cycles or redundant edges.

3. Step 3: Reject incorrect modifications

   Adding edges for all differing pairs or treating repeated chars as unique nodes breaks correctness or efficiency.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   First differing character edge addition is minimal and sufficient [OK]

Hint: Only first differing character pair defines order [OK]

Common Mistakes:

• Adding edges for all differing pairs causing cycles
• Using brute force all pairs approach losing efficiency
• Treating repeated chars as distinct nodes