Bus Routes

You are given an array routes representing bus routes where routes[i] is a bus route that visits a sequence of stops in a loop.

• Input: routes = [[1, 2, 7], [3, 6, 7]], source = 1, target = 6.
• Goal: Travel from source to target using the least number of buses.
• Rules: You can transfer between buses if they share a common stop.

This is a classic Shortest Path problem (Minimum number of edges/buses). This implies BFS.

Key Challenge:
If we treat Stops as nodes, a single route with 100 stops creates a 'clique' where every stop connects to every other stop. This leads to O(S^2) edges, which is too slow (TLE).

Optimized Graph:
Instead of Stop-to-Stop, think Bus-to-Bus or Stop-to-Bus.

1. Preprocessing: Build a Graph where key=Stop and value=List of Buses that stop there.
2. BFS Traversal:
   • Start at source stop.
   • Find all Buses at this stop.
   • Travel: For each bus, visit ALL its stops.
   • Optimization: Keep a visited set for Buses (Routes) to ensure we don't ride the same bus twice (avoids the clique problem).
   • Also keep visited for Stops to avoid checking the same stop redundantly.

Visualize buses as nodes in a graph. We hop from Bus to Bus via transfer stops.