Loading...
Loading...
Loading...
Rahul wants to visit his cousin during the semester break. The state has n cities, numbered 1 to n, and m bus routes. Each route runs both ways between two cities.
Rahul can change buses in any city. He starts in city s and wants to reach city t. Print YES if he can reach t, otherwise print NO. If s and t are the same city, he is already there.
YES or NO.Example 1
Input
5 3 1 2 2 3 4 5 1 3
Output
YES
Rahul goes 1 → 2 → 3, changing buses in city 2.
Example 2
Input
5 3 1 2 2 3 4 5 3 4
Output
NO
No route links the cities 1, 2, 3 with the cities 4, 5.
Try the problem first. Open one hint at a time.
Start in city s and visit every city you can reach. Then check whether t was visited.
Keep a visited array so the search never goes round a loop of routes forever.
Use a queue: take a city out, and add every neighbour that is not visited yet.
If s equals t, the answer is YES before any bus is taken.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor