LeetCode #1971 Easy

Find if Path Exists in Graph

Given an undirected graph as edge pairs and a source and destination, return whether a path exists between them.

graphdfsbfsunion-find

02

Intuition

The trap is forgetting the graph is undirected, so building the adjacency list needs both directions added for every edge -- add only one direction and a perfectly valid path silently disappears from the traversal. The other trap is source == destination: that is trivially a valid path of length zero, true even if the graph has no edges at all, so it must be checked before touching any edge data. Once both directions are wired up, a single DFS or BFS from the source that watches for the destination is the whole algorithm.

How to spot this pattern

Plain reachability — DFS or BFS from the source, stopping when the destination appears. The only detail that matters is building the adjacency list in both directions, since the edges are undirected.

03

Approach

1

Build the adjacency list both ways

For every edge [a, b], append b to adj[a] AND a to adj[b]. This is undirected -- skipping the second append means edges are only 'visible' from one endpoint, and some valid paths become invisible to the traversal.

2

Handle source == destination first

If source equals destination, the answer is true immediately, regardless of whether the graph has any edges connecting anything. This is a real edge case, not a formality.

3

DFS/BFS and stop the moment destination is seen

Otherwise walk the graph from source, marking visited vertices to avoid cycles, and stop as soon as destination is reached. If the traversal exhausts every reachable vertex without ever touching destination, no path exists.

04

Solution & live demo

▶1class Solution:
▶2    def validPath(self, n, edges, source, destination):
▶3        if source == destination:
▶4            return True
▶5        adj = [[] for _ in range(n)]
▶6        for a, b in edges:
▶7            adj[a].append(b)   # undirected: both directions
▶8            adj[b].append(a)
▶9        seen = [False] * n
▶10        def dfs(u):
▶11            if u == destination:
▶12                return True
▶13            seen[u] = True
▶14            for v in adj[u]:
▶15                if not seen[v] and dfs(v):
▶16                    return True
▶17            return False
▶18        return dfs(source)

05

Common pitfalls

Adding edges in one direction only

✗ Wrong

adj[a].append(b)

✓ Right

adj[a].append(b)
adj[b].append(a)

An undirected edge must be traversable from either endpoint. Storing one direction makes the graph directed and reports no path whenever the route needs to travel against an edge's insertion order.

Marking visited after recursing

✗ Wrong

for v in adj[u]:
    if not seen[v] and dfs(v): return True
seen[u] = True

✓ Right

seen[u] = True
for v in adj[u]:

Undirected edges are symmetric, so a neighbour immediately recurses back into u. Without the flag already set, that becomes infinite mutual recursion and the stack overflows.

Missing the trivial case

✗ Wrong

return dfs(source)

✓ Right

if source == destination:
    return True

When the two are the same vertex the answer is trivially true, but a DFS that marks before testing may not report it depending on the check's placement. Handling it up front removes the ambiguity.

06

Edge cases

source == destination

Return true immediately -- valid even with zero edges.

Destination in a separate component

DFS exhausts its component without finding it -- return false.

Edge only added in one direction (bug)

Both adj[a].append(b) and adj[b].append(a) are required for correctness.

Self-loop edge [a, a]

Harmless -- visited check prevents infinite recursion.

07

Complexity

Time

O(V + E)

Space

O(V + E)

Each vertex and edge visited at most once.