Find if Path Exists in Graph
Easy · Graphs · Depth-First Search · Breadth-First Search · Union Find · Graph
Problem
An undirected graph has n vertices labelled 0 to n - 1. Each edges[i] = [u, v] joins u and v in both directions. No vertex has an edge to itself, and no pair of vertices is joined twice.
Given two vertices source and destination, return true if some path leads from source to destination, and false otherwise.
Examples
Input: n = 5, edges = [[0,1],[1,2],[3,4]], source = 0, destination = 2 Output: true
0 reaches 2 through 1.
Input: n = 5, edges = [[0,1],[1,2],[3,4]], source = 1, destination = 4 Output: false
4 is in a separate component with 3; no edge leads there from 0, 1 or 2.
Input: n = 1, edges = [], source = 0, destination = 0 Output: true
A vertex always reaches itself, by a path of no edges.
Constraints
- 1 <= n <= 2 · 10^5
- 0 <= len(edges) <= 2 · 10^5
- edges[i] == [u, v] with 0 <= u, v < n and u != v
- 0 <= source, destination < n
- no edge appears twice
Approaches
- Sweep the edges until nothing changes — time O(n · m), space O(n)
Follow-up
What if many (source, destination) questions are asked about the same graph? Label every vertex with its component once (one search per component, or union-find), and then each question is a comparison of two labels.
Related problems
Start free on Cariara · Coding problems · System design studio
