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.

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

python

▶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

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.

06

Complexity

Time

O(V + E)

Space

O(V + E)

Each vertex and edge visited at most once.