Path Exists in a Graph
easyGraphs II+10 XPTime limit 2s
A town has n junctions joined by m two-way roads. Can you drive from junction s to junction t?
Input:
- line 1:
n m s t - next
mlines: a roadu v
Output: true if t can be reached from s, otherwise false. (A junction can always reach itself.)
Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ m ≤ 10⁵, 1 ≤ u, v, s, t ≤ n, u ≠ v. The nodes are numbered 1 … n.
Think about it: a BFS or DFS from s that stops when it meets t — or put every road into a Union-Find and check whether s and t end up with the same root. Use an explicit stack/queue: a recursive DFS can overflow on a long chain.
Sample input 1
6 5 1 4 1 2 2 3 4 5 5 6 6 4
Sample output 1
false
Sample input 2
3 2 1 3 1 2 2 3
Sample output 2
true
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).