图中点的层次

思路分析

本题是宽度优先搜索在图里的一个应用，本题边权重相等，求最短路，所以可以使用$bfs$算法

图采用邻接表存储

从一号点开始宽搜，拓展结点就是遍历它的每一个子节点

这里由于$bfs$最短路的性质，每一个点搜索过了就不需要第二次搜索，所以通过判重来剪枝，可以用一个$bool$类型的$st$[ ]来判断是否遍历过当前结点。不过这里用$d$[ ]来判重，当前结点没有走到过，距离就是-1，走过就会是一个非负数

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

int n, m;
int h[N], e[N], ne[N], idx;
int d[N]; // 距离 + 判重数组

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

int bfs()
{
    memset(d, -1, sizeof d);

    queue<int> q;
    d[1] = 0;
    q.push(1);

    while (q.size()) // 队列不空
    {
        int t = q.front();
        q.pop(); // 取出队头元素

        for (int i = h[t]; i != -1; i = ne[i]) // 遍历子节点，拓展
        {
            int j = e[i]; // 取出子节点编号
            if (d[j] == -1) // 不重复就入队
            {
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }

    return d[n];
}

int main()
{
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h); // 初始化

    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}