AcWing 847. 图中点的层次
原题链接
简单
图中节点的层次
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int n, m;
// 邻接表
int h[N], e[N], ne[N], idx;
// bfs队列
queue<int> q;
// 距离数组
int dist[N];
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int bfs() {
// 初始化距离数组
memset(dist, -1, sizeof dist);
// 起点入队
q.push(1);
dist[1] = 0;
while (!q.empty()) {
// 出队
int node = q.front();
q.pop();
// 顶点的邻边
for (int i = h[node]; i != -1; i = ne[i]) {
// 如果node相邻的顶点next_node没有被访问过
int next_node = e[i];
if (dist[next_node] == -1) {
q.push(next_node);
dist[next_node] = dist[node] + 1;
}
}
}
return dist[n];
}
/**
* acwing 847-图中节点的层次
* @return
*/
int main() {
cin >> n >> m;
// 初始化邻接表
memset(h, -1, sizeof h);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}