【图论】链式前向星实现图的BFS搜索
#include <iostream>
#include <cstring>
using namespace std;
//宽搜遍历图
const int N = 10001;
int head[N], next[N], to[N], idx;
int d[N], q[N];
int n, m;
inline void add(int u, int v) {
to[idx] = v, next[idx] = head[u], head[u] = idx++;
}
inline int dfs() {
int hh = 0, tt = 0;
//定义队头和队尾
q[0] = 1; // 起点 1
memset(d, -1, sizeof d); //d[u] 为 -1 表示没有宽度搜索过该结点
d[1] = 0; //d[u] 表示到达结点 u的最小距离
while (hh <= tt) { //队列不空
int t = q[hh ++]; //取得对头并出队
for (int i = head[t]; i != -1; i = next[i]) { //用 i 来遍历该节点所有指向的边
int j = to[i]; //j 表示边指向的值
if (d[j] == -1) { //如果该边指向的结点 j 没有被扩展过
d[j] = d[t] + 1; //用当前结点的最短路径计算到达该结点的最短路径
q[++ tt] = j; //该结点入队, 队尾指针后移并赋值
}
}
}
return d[n];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
// n表示结点数量 m 表示边的数量
memset(head, -1, sizeof head);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
add(u, v);
}
cout << dfs() << endl;
}