Find if Path Exists in Graph
Problem Statement
There is a bi-directional graph with n vertices labelled 0..n-1. You are given a 2D array edges where each edges[i] = [u, v] connects u and v. Each pair of vertices is connected by at most one edge, and no vertex connects to itself.
Given source and destination, return true if a valid path exists from source to destination, otherwise false.
Input
An integer n, an edge list edges, and two vertices source and destination.
Output
A boolean: whether source and destination are connected.
Constraints
- •
1 <= n <= 2 * 10^5 - •
0 <= edges.length <= 2 * 10^5 - •
edges[i].length == 2 - •
0 <= u, v, source, destination < n - •
There are no duplicate edges and no self-loops.
Examples
Example 1
n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
trueExample 2
n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
falseLearning Objectives
- Build an adjacency list from an edge list — the standard first step for non-grid graphs.
- Answer a reachability query with BFS/DFS from a single source.
- Meet Union-Find as an alternative that answers connectivity without an explicit traversal.
Intuition
The question is pure reachability: are source and destination in the same connected component? Two natural strategies:
Traversal. Convert the edge list to an adjacency list, then BFS/DFS outward from source, marking visited vertices. If you ever reach destination, the path exists. This is the direct, intuitive answer.
Union-Find. Notice you do not actually need the path — only whether the two vertices are connected. Union every edge's endpoints into the same set, then simply check whether source and destination share a root. This is the pattern to reach for when a problem asks only about connectivity, especially if edges arrive incrementally.
Common mistakes
- ×Adding edges in only one direction — the graph is undirected, so add both u→v and v→u.
- ×Marking a vertex visited when you dequeue it instead of when you enqueue it, allowing duplicates in the queue.
- ×Recursive DFS overflowing the stack for n up to 2·10^5 — prefer BFS or an explicit stack, or Union-Find.
- ×Forgetting the trivial case source == destination (both approaches handle it, but say so).
Algorithm Explanation
BFS: build adjacency lists, enqueue source (marked visited), and repeatedly pop a vertex and enqueue its unvisited neighbours; return true if destination is reached.
Union-Find: initialise each vertex as its own parent, union both endpoints of every edge, then return whether find(source) == find(destination). With path compression and union by rank each operation is near O(1) amortised.
Solutions
Solution 1: BFS over an adjacency list
Great default; also lets you recover the actual path if asked. Use an explicit queue to stay safe on large inputs.
Turn edges into adjacency lists, then breadth-first search from source, returning true the moment destination is dequeued or discovered.
Step-by-step
- Build adj as a list of lists and add each edge in both directions.
- BFS from source with a visited array, marking on enqueue.
- If a popped vertex equals destination, return true; if the queue empties first, return false.
O(V + E)
O(V + E)
Adjacency list stores every edge; the queue and visited array are O(V).
Java implementation
Solution 2: Union-Find (Disjoint Set Union)
Preferred when you only need connectivity (not the path), when there are many connectivity queries, or when edges are added incrementally.
Union both endpoints of every edge, then check whether source and destination resolve to the same root. Path compression keeps find nearly constant time.
Step-by-step
- parent[i] = i initially: every vertex is its own set.
- find follows parents to the root, compressing the path by pointing each node at its grandparent.
- union links the root of one set under the other.
- After unioning all edges, source and destination are connected iff they share a root.
O(V + E · α(V))
O(V)
α is the inverse-Ackermann function — effectively constant.
Java implementation
Dry Run
Sample input
n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5. Union-Find trace (root after each union):
| Edge | union | parent snapshot (roots) | Note |
|---|---|---|---|
| [0,1] | 0 ~ 1 | {0,1}→0 2→2 3→3 4→4 5→5 | component A grows |
| [0,2] | 0 ~ 2 | {0,1,2}→0 3,4,5 singletons | A = {0,1,2} |
| [3,5] | 3 ~ 5 | {3,5}→3 4→4 | component B starts |
| [5,4] | 5 ~ 4 | {3,4,5}→3 | B = {3,4,5} |
| [4,3] | 4 ~ 3 | no change | already same set |
find(0) = 0 and find(5) = 3. The roots differ, so source and destination are in different components → return false.
Interview Tips
Offer both approaches and explain the trade-off: BFS/DFS if they might ask for the actual path, Union-Find if the question is purely connectivity or if edges stream in over time. Emphasise building the adjacency list in both directions for an undirected graph. On huge inputs, call out the recursion-depth risk and default to iterative BFS or Union-Find.
Likely follow-ups
- Return the actual shortest path, not just whether one exists (BFS with a parent array).
- Support online edge additions with connectivity queries interleaved (Union-Find shines).
- Count the number of connected components (next module).
Similar Problems
Key Takeaways
- Reachability = 'are these two nodes in the same component?'
- Build undirected adjacency lists by adding each edge in both directions.
- Union-Find answers connectivity without building or walking an adjacency list.
- Prefer iterative BFS or Union-Find when n is large to avoid stack overflow.