Bird
Raised Fist0

Given the final order output [0, 2, 1, 3] from Kahn's Algorithm on 4 courses, and the in-degree array after processing is [0, 0, 0, 0], which of the following prerequisite pairs is consistent with this output?

hard🔄 Reverse Engineer Q9 of Q15
Topological Sort - Course Schedule II (Topological Order)
Given the final order output [0, 2, 1, 3] from Kahn's Algorithm on 4 courses, and the in-degree array after processing is [0, 0, 0, 0], which of the following prerequisite pairs is consistent with this output?
A[(1, 0), (2, 1), (3, 2)]
B[(1, 0), (2, 0), (3, 1)]
C[(0, 1), (2, 0), (3, 1)]
D[(3, 0), (1, 2), (2, 3)]
Step-by-Step Solution
Solution:
  1. Step 1: Verify order respects prerequisites

    In order [0,2,1,3], 0 before 1 and 2, and 1 before 3.
  2. Step 2: Check each option

    [(1, 0), (2, 0), (3, 1)] has (1,0), (2,0), (3,1) which matches order constraints.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Prerequisites consistent with order -> [(1, 0), (2, 0), (3, 1)] [OK]
Quick Trick: Prerequisite b before a means b appears before a in order [OK]
Common Mistakes:
MISTAKES
  • Confusing prerequisite direction
  • Not verifying order consistency
Trap Explanation:
PITFALL
  • Candidates often confuse which course must come first in prerequisite pairs.
Interviewer Note:
CONTEXT
  • Tests deep understanding of order and prerequisite relation.
Master "Course Schedule II (Topological Order)" 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