Find if Path Exists in Graph
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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
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)
