Find if Path Exists in Graph
Given n nodes labelled 0 to n - 1, a list of undirected edges, and two nodes source and destination, return True if a path exists between them, otherwise False.
Implement valid_path(n, edges, source, destination), where edges is a list of [u, v] pairs. In the example below, the input is shown as: first line = n, second = edges as u:v comma-separated (or 'none'), third = source destination.
Example
Input
3 0:1,1:2,2:0 0 2
Output
True
Reasoning
- Input: nodes labelled ; three undirected edges , , (each can be walked in either direction);
sourceanddestination. - The question is purely about reachability: is there some sequence of edges starting at node 0 and ending at node 2? Length and cost don't matter.
- Starting from node 0, its neighbours are . Node 2 is already among them, so the one-edge path exists. The two-edge route works too.
- In fact all three nodes form one connected component (a triangle), so every pair of nodes here is reachable from each other.
- Output:
True, a boolean, because 0 and 2 lie in the same component. - Notice the answer is
Falseexactly when the two nodes sit in different components, e.g. a graph split into and withsource,destination. And whensourceequalsdestination, the empty path counts, so the answer isTrue.
Constraints
- 1 <= n <= 2 * 10^5
- 0 <= edges.length <= 2 * 10^5