815. Bus Routes

https://leetcode.com/problems/bus-routes/description/

给定一系列公交车路线，每个公交车可以不下车循环坐，问从S站点到T站点需要最少乘多少辆车。问的是最小换乘而不是最少站点，因此循环坐车可看做从该公交车路线任意站点无需换乘就能到达路线上的其它任意站点，也就是图上直接相连。最少次数，而且又给定了图，BFS。

/*
 * @lc app=leetcode id=815 lang=cpp
 *
 * [815] Bus Routes
 */

// @lc code=start
class Solution {
public:
    int numBusesToDestination(vector<vector<int>>& routes, int S, int T) {
        if (S == T) return 0;
        const int N = routes.size();
        unordered_map<int, vector<int>> stops;
        for (int i = 0; i < N; ++i) {
            for (const auto s : routes[i]) {
                stops[s].push_back(i);
            }
        } 
        vector<bool> visited(N, false);
        queue<int> q;
        q.push(S);
        int res = 0;
        while (!q.empty()) {
            ++res;
            for (int i = q.size() - 1; i >= 0; --i) {
                const auto t = q.front(); q.pop();
                for (const auto b : stops[t]) {
                    if (visited[b]) continue;
                    visited[b] = true;
                    for (const auto s : routes[b]) {
                        if (s == T) return res;
                        q.push(s);
                    } 
                }
            }
        }
        return -1;
    }
};
// @lc code=end