Bird
Raised Fist0

Given the following graph: [[1,2],[2,3],[5],[0],[5],[],[]], what is the output of the optimal approach (reverse graph + Kahn's algorithm) to find eventual safe states?

easy🧾 Code Trace Q3 of Q15
Topological Sort - Find Eventual Safe States
Given the following graph: [[1,2],[2,3],[5],[0],[5],[],[]], what is the output of the optimal approach (reverse graph + Kahn's algorithm) to find eventual safe states?
A[5,6]
B[0,1,2,3]
C[0,1,2,4,5,6]
D[2,4,5,6]
Step-by-Step Solution
Solution:
  1. Step 1: Build reverse graph and in-degree

    Reverse edges and compute in-degree: nodes 5 and 6 have zero out-degree, so queue starts with [5,6].
  2. Step 2: Process queue and update in-degree

    Process 5 and 6, decrement in-degree of their predecessors, adding nodes 2 and 4 when their in-degree reaches zero, then nodes 1 and 0 as their in-degree reaches zero.
  3. Step 3: Collect safe nodes

    After processing, safe nodes are [0,1,2,4,5,6].
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Safe nodes are [0,1,2,4,5,6] after topological processing [OK]
Quick Trick: Start from zero out-degree nodes in reversed graph [OK]
Common Mistakes:
MISTAKES
  • Miscounting in-degree
  • Not sorting final safe nodes
Trap Explanation:
PITFALL
  • Candidates often forget to reverse the graph or miscalculate in-degree, leading to incorrect safe nodes.
Interviewer Note:
CONTEXT
  • Tests ability to trace BFS topological sort on reversed graph with typical input.
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