Go as far as you can, then back up
Explore a graph like a maze, marking the places you've been so you never go round in circles. About 14 minutes.
Leave breadcrumbs
There is one danger in a maze with loops: you could walk round and round the same rooms forever. The cure is breadcrumbs. Drop one in every room you enter, and never enter a room that already has one.
To answer "can I get from here to there?", start at the first node and look at each neighbour in turn. If a neighbour has no breadcrumb, step into it and do the same there. If you ever stand on the target, the answer is yes. If you run out of doors everywhere, the answer is no.
adj = [[] for _ in range(n)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
seen = [False] * n
def visit(node):
if node == target:
return True
seen[node] = True
for nxt in adj[node]:
if not seen[nxt] and visit(nxt):
return True
return False
return visit(start)Start at 0 and drop a breadcrumb. We are looking for 3.
Two kinds of answer
When the search reaches the target it says yes, and that yes travels back up through every step that led there. When a node has no unseen neighbours left, it says no to whoever sent it, and that caller tries its next neighbour.
Nodes the search never reaches are not connected to the start at all, like a separate island. That is also an answer: if everything reachable has been explored and the target wasn't found, it is not reachable.
The search is standing on a node whose neighbours all have breadcrumbs already, and it isn't the target. What does it do?
- ABacks up to the node it came from and tries that node's next neighbour
- BWalks through the breadcrumb nodes again
- CStops and answers no for the whole graph
Show the answer
Backs up to the node it came from and tries that node's next neighbour. A dead end means no new places from here, so the search returns and tries other doors.
Can you get there?
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. Return whether you can travel from place start to place target along the roads.
n = 6, edges = [[0, 1], [0, 2], [1, 2], [2, 3], [4, 5]], start = 0, target = 3 → true
1 ≤ n ≤ 500 · 0 ≤ roads ≤ 5,000 · no road joins a place to itself