Find if Path Exists in Graph

Easy#1971

There are n vertices and a list of undirected edges. Say whether you can walk from the vertex source to the vertex destination along the edges. Our example: 5 vertices, edges 0–1, 2–3, 1–2, from 0 to 3 → true.

1971 Find if Path Exists in GraphWalkthrough · 1×

Example: 5 vertices, edges 0–1, 2–3, 1–2, source 0, destination 3. No edge joins 0 and 3: the path goes through 1 and 2.

012340011223344parentedges0–12–31–2source = 0, destination = 3
looking at nowroot of a groupedge already added

Each of the 5 vertices is its own root: 5 groups of one

01/49
restart · back · play · step
Speed
1function validPath(n, edges, source, destination):
2 parent = [0, 1, ..., n - 1]
3 for (a, b) in edges:
4 rootA = find(a)
5 rootB = find(b)
6 if rootA is not rootB:
7 parent[rootB] = rootA
8 rootS = find(source)
9 rootD = find(destination)
10 return rootS == rootD
11
12function find(x):
13 while parent[x] is not x:
14 x = parent[x]
15 return x
state
parent
[0, 1, 2, 3, 4]
a
–
b
–
rootA
–
rootB
–
rootS
–
rootD
–
x
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. An edge puts its two ends in one group, and joining two groups never splits anything, so after all edges a group is exactly a set of vertices that can reach each other.
  2. A group is named by its root. Two vertices are in one group when find gives them the same root, however many edges lie between them.
  3. The paths themselves are never built: the answer is one comparison of two roots.

Complexity

Time O(n + m · h) for m edges, where h is the height of the trees: up to n with this plain find, and almost a constant once find re-hangs the vertices it passes straight on the root and the smaller tree goes under the bigger one. Memory O(n) for parent.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.