Bus Route Rides Problem

Bus Route Rides Problem — ExecCode Hard DSA Practice

Solve the Bus Route Rides problem on ExecCode. Free online hard DSA practice in Graph. Write and run code in Java, C++, Python — no signup required to run.

Problem description

Each bus route is a cycle of stops. You may ride a whole route for cost 1 and transfer at shared stops. Find the minimum number of buses (not stops) to go from source to target. Modeling stops as nodes with huge degree TLE; BFS on buses is the OA insight. Return the fewest buses to ride, 0 if source == target, or -1 if impossible. You are given: routes — list of routes, each a list of stop ids source — start stop target — goal stop Return integer rides or -1. Source and target need not be in the same route.

Examples

Input {'routes': [[1, 2, 7], [3, 6, 7]], 'source': 1, 'target': 6}; Output 2. Input {'routes': [[7, 12], [4, 5, 15], [6]], 'source': 15, 'target': 12}; Output -1. Input {'routes': [[1, 2], [2, 3]], 'source': 1, 'target': 1}; Output 0

Constraints

Riding one route costs 1 regardless of how many stops you travel on it You may transfer only at intersecting stops

Practice Bus Route Rides free on ExecCode. Browse DSA problems, topic map, and placement guides.