> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/search/815.-bus-routes.md).

# 815. Bus Routes

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

```cpp
/*
 * @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


```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://hao-fu-1.gitbook.io/oj/search/815.-bus-routes.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.