LeetCode Solutions

Time: $O(n^2)$, where $n = |\texttt{routes}|$

Space: $O(n^2) + \Sigma |\texttt{routes[i]}|$

			

class Solution {
 public:
  int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
    if (S == T)
      return 0;

    unordered_map<int, vector<int>> graph;  // {route: [buses]}
    unordered_set<int> usedBuses;

    for (int i = 0; i < routes.size(); ++i)
      for (const int route : routes[i])
        graph[route].push_back(i);

    int ans = 0;
    queue<int> q{{S}};

    while (!q.empty()) {
      ++ans;
      for (int sz = q.size(); sz > 0; --sz) {
        const int route = q.front();
        q.pop();
        for (const int bus : graph[route])
          if (usedBuses.insert(bus).second)
            for (const int nextRoute : routes[bus])
              if (nextRoute == T)
                return ans;
              else
                q.push(nextRoute);
      }
    }

    return -1;
  }
};

			

class Solution {
  public int numBusesToDestination(int[][] routes, int S, int T) {
    if (S == T)
      return 0;

    Map<Integer, List<Integer>> graph = new HashMap<>(); // {route: [buses]}
    Set<Integer> usedBuses = new HashSet<>();

    for (int i = 0; i < routes.length; ++i)
      for (final int route : routes[i]) {
        graph.putIfAbsent(route, new ArrayList<>());
        graph.get(route).add(i);
      }

    int ans = 0;
    Queue<Integer> q = new ArrayDeque<>(Arrays.asList(S));

    while (!q.isEmpty()) {
      ++ans;
      for (int sz = q.size(); sz > 0; --sz) {
        for (final int bus : graph.get(q.poll()))
          if (usedBuses.add(bus))
            for (final int nextRoute : routes[bus])
              if (nextRoute == T)
                return ans;
              else
                q.offer(nextRoute);
      }
    }

    return -1;
  }
}

			

class Solution:
  def numBusesToDestination(self, routes: List[List[int]], S: int, T: int) -> int:
    if S == T:
      return 0

    graph = defaultdict(list)
    usedBuses = set()

    for i in range(len(routes)):
      for route in routes[i]:
        graph[route].append(i)

    ans = 0
    q = deque([S])

    while q:
      ans += 1
      for _ in range(len(q)):
        for bus in graph[q.popleft()]:
          if bus in usedBuses:
            continue
          usedBuses.add(bus)
          for nextRoute in routes[bus]:
            if nextRoute == T:
              return ans
            else:
              q.append(nextRoute)

    return -1