← Back to DSA Animator
Find if Path Exists in Graph LC #1971 Easy Graph · Union-Find
Problem

There is a bi-directional graph with n vertices labeled 0 to n-1. Given source and destination, return true if there is a valid path from source to destination.

Example 1
Input: n=3, edges=[[0,1],[1,2],[2,0]], source=0, destination=2
Output: true
Try Examples
Custom: n / edges (a-b) / src / dst
Approach
Union-Find (Disjoint Set Union)
Each node starts as its own parent. union(a,b) connects components. Path exists iff find(src) == find(dst) (same component).
Graph & Parent Array
Load an example to begin.
Variables
Edge
—
find(a)
—
find(b)
—
parent[]
—
Step Logic
Press ▶ Play or Next Step to begin.
✓
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Initialize parent[i]=i for all nodes
2
For each edge (a,b): union(parent, a, b)
3
Path exists iff find(parent,src)==find(parent,dst)
Time
O(n·α(n))
Space
O(n)
Why Union-Find

Union-Find tracks connected components. After processing all edges, src and dst are in the same component iff they're connected. Path compression makes lookups near O(1).