[Graph BFS/DFS] Course Schedule

[sudosf]

Problem

There are n courses. Given prerequisites as pairs [a, b] meaning b must be taken before a, determine if it is possible to finish all courses (i.e. no cycle exists).

References

• LeetCode: https://leetcode.com/problems/course-schedule/
• GFG: https://www.geeksforgeeks.org/problems/detect-cycle-in-a-directed-graph/1
• Sheet: https://www.risingbrain.org/sheet#graph (BFS/DFS section)
• Parent: Pattern: Graph - BFS and DFS Traversals #122

Difficulty

🟡 Medium

Companies

Amazon, Google, Goldman Sachs

Notes

Language: Java
Topological sort / cycle detection in directed graph. BFS (Kahn's algorithm using in-degree) or DFS with three-state coloring (unvisited/visiting/visited).