Is there a loop?
Spot a loop in a network of two-way roads by noticing when a road leads to a place you already reached some other way. About 14 minutes.
A second way to the same place
Run a normal search, marking places as you reach them. Every time you look along a road, one of three things is true. It leads back along the road you just came by. Or it leads to a place you haven't seen. Or it leads to a place you already reached.
The first is harmless and ignored. The second is normal. The third is the giveaway: you now have two different ways to reach that place, so there is a loop.
adj[u].append((v, edge_id)) # remember the road
Start at 0 and mark it. We arrived by no road.
Remember the road, not the place
Notice we say the road you arrived by, not the place. If two different roads join the same pair of places, then going along one and back along the other is a loop of length two. Skipping by place would hide it, but skipping by the specific road finds it.
The network might also have several separate pieces. Start a new search from every place not yet seen, so no piece is missed.
if edge_id == came_by:
continue # not back along itFrom place A you look along a road and find place B has been reached already, by a road that isn't the one you arrived on. What does that mean?
- AThere is a loop in the network
- BNothing, this is normal
- CYou've reached a dead end
Show the answer
There is a loop in the network. B can be reached two different ways, which together form a loop.
Is there a loop?
There are n places, numbered 0 to n − 1, joined by two-way roads. edges[i] = [a, b] means a road between place a and place b. Two different roads may join the same pair of places, and a road may even start and end at the same place. A loop is a trip that starts and ends at one place without using any road twice. Return true if the network contains a loop.
n = 5, edges = [[0, 1], [1, 2], [2, 0], [2, 3], [3, 4]] → true
1 ≤ n ≤ 100,000 · 0 ≤ roads ≤ 200,000