Waiting in a circle
Find a cycle in a directed graph by tracking which places are on the path you are currently walking. About 15 minutes.
A returning one-way road
Tasks that wait on other tasks form a directed graph. If task A waits for B, B waits for C, and C waits for A, nothing can ever start. That is a cycle, and finding one is a very common need.
Walk depth-first from a place. As you go deeper, you are building a current path. If a road leads back to a place that is on this very path, you've found a cycle. But if it leads to a place you visited earlier and finished, no cycle is proven.
state = [0] * n # 0 new, 1 busy, 2 done state[node] = 1
- path
- 0
Enter 0. It is on the path.
Three states
Give every place a state. Zero means unseen. One means the search is currently inside it, somewhere on the path from the start to now. Two means it and everything reachable from it has been fully explored, with no cycle found.
Mark a place as one when you enter it and as two when you leave it. A road to a one is a cycle, a road to a two is safe, and a road to a zero means go deeper. Start a search from every unseen place so no piece is missed.
if state[nxt] == 1:
return True # back on this walkYou follow a road to a place that you already finished exploring earlier, in another branch. Is that a cycle?
- ANo, the place isn't on your current path
- BYes, you've been there before
- CYou can't tell without exploring again
Show the answer
No, the place isn't on your current path. A finished place can't lead back to where you are now, or its exploration would have found it.
Waiting in a circle
There are n tasks, numbered 0 to n − 1. waits[i] = [a, b] means task a cannot finish until task b has finished (a one-way dependency). Return true if some tasks wait on each other in a circle, so that none of them can ever finish, and false if there is no circle.
n = 4, waits = [[0, 1], [1, 2], [2, 3], [3, 1]] → true
1 ≤ n ≤ 500 · 0 ≤ waits ≤ 5,000