BFS【东北大学oj数据结构11-3】C++

题面

对于给定的有向图 G = (V, E)，编写一个程序来找出从顶点 1 到每个顶点的最短距离 d（路径上的最小边数）。每个顶点从 1 到 n 编号。 对于不能从顶点 1 到达的顶点，输出 -1。

输入

第一行给出了 G 中的顶点数 n。 接下来的 n 行给出了每个顶点 u 的邻接表，格式如下：

ukv1​v2​…vk​

u 是顶点的编号，k 是 u 的度数，v1​v2​…vk​是与 u 相邻的顶点的编号。

约束
1≤n≤100

输出

在一行上输出每个顶点的 id 和 d。 id 是顶点的编号，d 是顶点 1 到该顶点的距离。 按顶点编号顺序输出。

输入样例

4
1 2 2 4
2 1 4
3 0
4 1 3

输出样例

1 0
2 1
3 2
4 1 

代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm> 
 
using namespace std;
 
// BFS函数，接受图的邻接表和起始节点
void bfs(int start, const vector<vector<int>>& adj, vector<int>& visited,int n) {
    queue<int> q;
    q.push(start);
    visited[start] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
 
        for (int v : adj[u]) {
            if (visited[v]==-1) {
                visited[v] = visited[u]+1;
                q.push(v);
            }
        }
    }
 
    cout << endl;  
}
 
int main() {
    int n;
    cin >> n;
 
    vector<vector<int>> adj(n);
    vector<int> visited(n, -1);
 
    for (int i = 0; i < n; ++i) {
        int u, k;
        cin >> u >> k;
        u--;
        for (int j = 0; j < k; ++j) {
            int v;
            cin >> v;
            v--;
            adj[u].push_back(v);
        }
    }
 
    bfs(0,adj,visited,n);
    for(int i=0;i<n;i++)
    {
        cout <<(i+1)<<" "<<visited[i]<<endl;
    }
    return 0;
}