25 / 75
Medium
Course Schedule
#25graphtopological-sortdfsbfscycle-detection
Detect if course prerequisites form a cycle using topological sort or DFS cycle detection.
Example:
Input:
numCourses=2, prerequisites=[[1,0]]Output:
true (take course 0, then course 1)Common Mistakes:
- Using only two states (visited/unvisited) instead of three states for cycle detection
- Building graph in wrong direction (prerequisites relationship)
- Not checking all components if graph is disconnected
- Confusing this with Course Schedule II (which asks for order)
Notes:
Classic cycle detection in directed graph. Time O(V+E), Space O(V+E). Can also use Kahn's algorithm (BFS topological sort) with in-degree array.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Detect if course prerequisites form a cycle using topological sort or DFS cycle detection.
Example:
Input:
numCourses=2, prerequisites=[[1,0]]Output:
true (take course 0, then course 1)Common Mistakes:
- Using only two states (visited/unvisited) instead of three states for cycle detection
- Building graph in wrong direction (prerequisites relationship)
- Not checking all components if graph is disconnected
- Confusing this with Course Schedule II (which asks for order)
Notes:
Classic cycle detection in directed graph. Time O(V+E), Space O(V+E). Can also use Kahn's algorithm (BFS topological sort) with in-degree array.
25/75
Course Schedule