【模板题】树与图的广度优先遍历

一、AcWing 847. 图中点的层次

【题目描述】
给定一个$n$个点$m$条边的有向图，图中可能存在重边和自环。
所有边的长度都是$1$，点的编号为$1\sim n$。
请你求出$1$号点到$n$号点的最短距离，如果从$1$号点无法走到$n$号点，输出$-1$。

【输入格式】
第一行包含两个整数$n$和$m$。
接下来$m$行，每行包含两个整数$a$和$b$，表示存在一条从$a$走到$b$的长度为$1$的边。

【输出格式】
输出一个整数，表示$1$号点到$n$号点的最短距离。

【数据范围】
$1\le n,m\le 10^5$

【输入样例】

4 5
1 2
2 3
3 4
1 3
1 4

【输出样例】

1

【代码】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

const int N = 100010, M = 100010;
int e[M], ne[M], h[N], idx;
int n, m, dis[N];

void add(int u, int v)
{
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

int bfs()
{
    memset(dis, -1, sizeof dis);
    queue<int> Q;
    dis[1] = 0;
    Q.push(1);
    while (Q.size())
    {
        int t = Q.front();
        Q.pop();
        for (int i = h[t]; ~i; i = ne[i])
            if (!~dis[e[i]]) Q.push(e[i]), dis[e[i]] = dis[t] + 1;
    }
    return dis[n];
}

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;
}