n intersections numbered 0 to n - 1 and one-way roads roads: a pair [a, b] is a road from a to b. A road may lead back to the same intersection, and the same road may be listed more than once.
A courier leaves intersection start and keeps taking any available road until reaching an intersection with no roads out. Return True if, whatever choices the courier makes:
- the trip is guaranteed to end (there is no way to drive around forever);
- it can only end at intersection goal.
Otherwise return False. In particular, if any road leaves goal, the courier can never stop there.n=4, roads=[[0, 1], [0, 2], [1, 3], [2, 3]], start=0, goal=3 → True
From 0 you can go to 1 or 2, but both routes meet at 3, which has no roads out.
n=3, roads=[[0, 1], [1, 0], [0, 2]], start=0, goal=2 → False
You can loop 0 → 1 → 0 forever, so there are infinitely many routes.
n=3, roads=[[0, 1], [0, 2]], start=0, goal=2 → False
Going to 1 leaves you stuck at a dead end that is not the goal.
n=4, roads=[[0, 1], [0, 2], [1, 3], [2, 3]], start=0, goal=3
True
Run checks the first 3 tests in your browser. Submit checks all 75 tests on the server, hidden ones included.