Bird
Raised Fist0

The following code attempts to find eventual safe states using the reversed graph and Kahn's algorithm. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium🐞 Bug Identification Q14 of Q15
Topological Sort - Find Eventual Safe States
The following code attempts to find eventual safe states using the reversed graph and Kahn's algorithm. Identify the line containing the subtle bug that causes incorrect results on some inputs.
from collections import deque

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

    for u in range(n):
        for v in graph[u]:
            reverse_graph[v].append(u)
        in_degree[u] = len(graph[u])  # Bug fixed here

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

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

    return sorted(safe)
ALine initializing queue with nodes having in_degree zero
BLine appending u to reverse_graph[v]
CLine decrementing in_degree[prev] inside the while loop
DLine setting in_degree[v] = len(graph[u]) inside the outer loop
Step-by-Step Solution
Solution:
  1. Step 1: Identify in-degree assignment error

    In-degree should be assigned per node u, but the original code assigned in_degree[v] inside inner loop, overwriting multiple times incorrectly.
  2. Step 2: Correct assignment

    It should be in_degree[u] = len(graph[u]) after inner loop completes, not in_degree[v].
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Incorrect in-degree causes wrong queue initialization and wrong safe nodes [OK]
Quick Trick: In-degree must be assigned per node, not per neighbor [OK]
Common Mistakes:
MISTAKES
  • Confusing in-degree and out-degree assignment
  • Assigning in-degree inside inner loop incorrectly
  • Misusing loop variables for in-degree
Trap Explanation:
PITFALL
  • Assigning in-degree[v] inside inner loop looks plausible but corrupts in-degree counts.
Interviewer Note:
CONTEXT
  • Tests candidate's attention to detail and understanding of graph in-degree construction.
Master "Find Eventual Safe States" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes