Skills101
← All coding problems

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 m lines: a road u 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).

Loading editor…

Log in to run and submit your code — it's free.