Course schedule (cycle check)
We'll cover the following
Courses have prerequisites "a>b". Can all courses be finished, or do some depend on each other in a loop?
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
–0
–1
–2
–3
–4
–5
–6
–7
–8
–9
–10
–11
– not visited, ● on the current path, ✓ finished. A cycle exists only if we reach a ● node again.
1 / 14
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(V + E) | O(V + E) | Each node is finished once; the recursion holds the current path. |
In Python
def can_finish(n, edges):
adj = [[] for _ in range(n)]
for u, v in edges: adj[u].append(v)
state = [0] * n # 0 new, 1 on path, 2 done
def dfs(u):
state[u] = 1
for v in adj[u]:
if state[v] == 1 or (state[v] == 0 and dfs(v)): return True
state[u] = 2
return False
return not any(state[i] == 0 and dfs(i) for i in range(n))Summary: say it in the interview
- Walk depth first and mark nodes: not visited, on the current path, finished. Reaching a node that is still on the current path means you looped back. Finished nodes can be skipped. Try deleting the last edge to see a clean run.
- Time O(V + E), space O(V + E). Each node is finished once; the recursion holds the current path.