Find if Path Exists in Graph
Easy· BFS· Union-Find
Problem
An undirected graph has n vertices labelled 0 to n - 1 and a list of edges. Determine whether there is any path from a given source vertex to a given destination vertex.
Examples
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
Vertices 0-2 and 3-5 form two separate components.
Constraints
- • 1 <= n <= 2 * 10^5
- • 0 <= edges.length <= 2 * 10^5
- • No duplicate edges or self-loops
Hints & approach
Hint 1
Build an adjacency list from the edge list.
Hint 2
Any traversal from source that marks visited nodes will tell you if destination is reachable.
Hint 3
Union-find also works: the answer is whether source and destination share a root.
Approachtry the hints first
Build an adjacency list, then BFS or DFS from source with a visited array, returning true as soon as destination is reached. Alternatively, union the endpoints of every edge in a disjoint-set structure and compare the roots of source and destination. Both run in linear time in vertices plus edges.
Time O(n + e) · Space O(n + e)