Bird
Raised Fist0

Which of the following statements about adapting the BFS topological sort approach is correct?

hard🎤 Interviewer Follow-up Q15 of Q15
Topological Sort - Parallel Courses (Minimum Semesters)
Suppose the problem is modified so that some courses can be taken multiple times (repeatedly) and prerequisites must be satisfied each time before retaking. Which of the following statements about adapting the BFS topological sort approach is correct?
AWe should switch to a dynamic programming approach because BFS topological sort cannot handle repeated courses.
BThe original BFS topological sort can be used without changes since it handles cycles by returning -1.
CWe can use BFS topological sort by resetting indegrees after each semester and reprocessing courses as needed.
DThe problem becomes invalid because repeated courses create cycles; BFS topological sort cannot be applied directly.
Step-by-Step Solution
  1. Step 1: Understand repeated courses and prerequisites

    Allowing repeated courses with prerequisites means cycles can form because a course depends on itself indirectly.
  2. Step 2: Analyze BFS topological sort applicability

    BFS topological sort requires a DAG; cycles break this assumption, so it cannot be applied directly.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Repeated courses induce cycles -> BFS topological sort invalid [OK]
Quick Trick: Repeated courses create cycles, breaking DAG assumption [OK]
Common Mistakes:
MISTAKES
  • Assuming BFS topological sort handles cycles by returning -1
  • Thinking resetting indegrees can simulate repeats correctly
  • Believing DP is always needed without analyzing graph structure
Trap Explanation:
PITFALL
  • Candidates may think BFS topological sort can be reused by resetting states, but cycles invalidate the approach.
Interviewer Note:
CONTEXT
  • Tests candidate's understanding of problem constraints and algorithm limitations under variant conditions.
Master "Parallel Courses (Minimum Semesters)" 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