Several cities are connected by two-way roads.

Determine whether a traveler can reach an arrival city from a departure city.

Class

RoadTripPlanner

Method

isTripPossible

boolean isTripPossible( int cityCount, List<String> roads, int departureCity, int arrivalCity )

Parameters

• cityCount: The total number of cities.
• roads: The direct two-way roads between cities.
• departureCity: The city where the journey begins.
• arrivalCity: The city the traveler wants to reach.

Road Format

Each road is represented by a string in the format "firstCity,secondCity".

For example, "2,5" represents a two-way road between cities 2 and 5.

Returns

Return true if the traveler can reach arrivalCity from departureCity.

Return false if no such route exists.

Travel Rules

• Cities are numbered from 0 to cityCount - 1.
• Every road can be traveled in both directions.
• The journey may pass through any number of intermediate cities.
• The traveler does not need a direct road between the departure and arrival cities.
• If departureCity equals arrivalCity, return true.

Constraints

• 1 ≤ cityCount ≤ 200,000
• 0 ≤ roads.size() ≤ 200,000
• Every value in roads has the format "firstCity,secondCity".
• 0 ≤ firstCity, secondCity < cityCount
• firstCity != secondCity
• 0 ≤ departureCity, arrivalCity < cityCount
• No pair of cities has more than one direct road.
• No parameter value is null.

Example 1

isTripPossible( cityCount = 9, roads = List.of( "0,4", "4,7", "7,2", "1,5", "5,8", "8,6" ), departureCity = 0, arrivalCity = 2 )

Output: true

The traveler can follow the route 0 → 4 → 7 → 2.

Example 2

isTripPossible( cityCount = 7, roads = List.of( "0,1", "1,3", "2,4", "4,6" ), departureCity = 3, arrivalCity = 6 )

Output: false

Cities 3 and 6 belong to separate road networks, so no route connects them.

Example 3

isTripPossible( cityCount = 5, roads = List.of(), departureCity = 2, arrivalCity = 2 )

Output: true

The traveler is already in the arrival city, so no road is required.