1971. Find if Path Exists in Graph¶
Edited by Charles
Easy · Python · Graph
Problem
Read the original problem on LeetCode.
The official page contains the problem statement, examples, and constraints.
Explanation, examples & other approaches
Core idea
This problem asks whether there exists a valid path from source to destination in an undirected graph.
We can solve it using Union Find (Disjoint Set Union / DSU).
Original study notes follow, including intermediate snippets and earlier attempts.
Idea¶
This problem asks whether there exists a valid path from source to destination in an undirected graph.
We can solve it using Union Find (Disjoint Set Union / DSU).
The key idea is:
If two nodes are connected by a path, they will eventually belong to the same set and have the same root.
Therefore, we can:
1. Initialize every node as its own set.
2. Traverse all edges.
3. Union the two nodes of each edge.
4. Check whether source and destination have the same root.
Union Find Structure¶
We use a parent array to represent the sets.
Initially:
For example, if:
then:
This means every node initially belongs to its own set:
Find¶
The find(x) function finds the root of node x.
def find(self, x):
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
The line:
performs path compression.
For example, suppose:
After calling:
the structure can become:
This makes future find operations much faster.
Union¶
To connect two nodes x and y, first find their roots:
If they already have the same root:
they are already in the same set.
Otherwise, connect one root to the other:
So:
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_y] = root_x
Important: Union Does Not Connect Every Node Into One Set¶
When we traverse:
we are not necessarily connecting every node to one root.
We only merge sets when an edge connects them.
For example:
Initially:
After:
we have:
After:
we have:
Then the remaining edges connect 3, 4, and 5:
So there are still two separate sets.
This correctly represents the two connected components of the graph.
Why Does This Tell Us Whether a Path Exists?¶
Consider:
After processing all edges, Union Find may represent the graph as:
Therefore:
and:
If:
then:
so a path exists.
But if:
then:
so no path exists.
Therefore:
Why Can We Union Each Edge?¶
The graph is undirected.
An edge:
means:
Therefore, u and v must belong to the same connected component.
We can simply call:
Unlike an adjacency list, we do not need to separately store:
because Union Find only cares whether the two nodes belong to the same set.
Solution Structure¶
We first create a reusable UnionFind class:
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x):
if x != self.parent[x]:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x != root_y:
self.parent[root_y] = root_x
def is_same(self, x, y):
return self.find(x) == self.find(y)
Then the actual problem becomes very simple:
class Solution:
def validPath(
self,
n: int,
edges: List[List[int]],
source: int,
destination: int
) -> bool:
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.is_same(source, destination)
Hand Simulation¶
Consider:
Initially:
Process [0, 1]¶
Roots:
Merge them:
Process [1, 2]¶
First:
So we are actually merging the two roots:
After union:
Process [2, 0]¶
Both already have the same root:
Therefore, nothing needs to be changed.
Finally:
checks:
Therefore:
Union Find vs DFS/BFS¶
This problem can also be solved using DFS or BFS.
DFS / BFS¶
The idea is:
Union Find¶
The idea is:
Process every edge
↓
Merge connected nodes into sets
↓
Do source and destination have the same root?
So:
DFS / BFS
→ directly search for a path
Union Find
→ determine whether two nodes belong to the same connected component
For this problem, both approaches work.
Complexity Analysis¶
Let:
With path compression, Union Find operations are very efficient.
Processing all edges requires approximately:
where α(V) is the inverse Ackermann function.
In practice, α(V) is extremely small, so this is almost:
Space complexity:
for the parent array.
Summary¶
1. Initialize every node as its own set.
2. For every edge [u, v]:
union(u, v)
3. union() finds the roots of u and v
and merges their sets.
4. After processing all edges,
each connected component has a common root.
5. Check:
find(source) == find(destination)
6. Same root → path exists
Different root → path does not exist
The most important idea is:
Union Find does not necessarily merge all nodes into one set. It merges exactly the nodes that belong to the same connected component.
Therefore:
Two nodes are connected if and only if they have the same root.
Study record
| Field | Value |
|---|---|
| Attempts | 1 |
| Mastery | ❚ |
| The Latest Attempt | August 23, 2026 |
Python solution¶
class UnionFind:
def __init__(self, size):
self.parent = list(range(size))
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, node1, node2):
root1 = self.find(node1)
root2 = self.find(node2)
if root1 == root2:
return
self.parent[root1] = root2
def isSame(self, node1, node2):
return self.find(node1) == self.find(node2)
class Solution:
def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return uf.isSame(source, destination)