【BFS】图中点的层次

题目

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

解题

方法一：BFS

思路

存图。

套用BFS模板求解。

代码

#include <iostream>
#include <cstring>


using namespace std;

const int N = 1e5 + 10;
int h[N], e[N], ne[N], idx;
bool vis[N];
int n, m;
int que[N], hh, tt = -1;

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

int bfs() {
    que[++tt] = 1;
    vis[1] = true;
    int step = 0;
    while (hh <= tt) {
        int size = tt - hh + 1;
        while (size--) {
            int curr = que[hh++];
            if (curr == n) return step;
            for (int i = h[curr]; i; i = ne[i]) {
                int j = e[i];
                if (!vis[j]) {
                    que[++tt] = j;
                    vis[j] = true;
                }
            }
        }
        ++step;
    }
    return -1;
}

int main() {
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }
    printf("%d\n", bfs());
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int n, m, idx;
    static int[] heads, vals, nexts;
    
    static void add(int a, int b) {
        vals[idx] = b;
        nexts[idx] = heads[a];
        heads[a] = idx++;
    }
    
    static int bfs() {
        boolean[] vis = new boolean[n + 1];
        int[] que = new int[2 * m];
        int hh = 0, tt = -1;
        que[++tt] = 1;
        vis[1] = true;
        int step = 0;
        while (hh <= tt) {
            int size = tt - hh + 1;
            while (size-- > 0) {
                int curr = que[hh++];
                if (curr == n) return step;
                for (int i = heads[curr]; i != -1; i = nexts[i]) {
                    int j = vals[i];
                    if (!vis[j]) {
                        que[++tt] = j;
                        vis[j] = true;
                    }
                }
            }
            ++step;
        }
        return -1;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        heads = new int[n + 1];
        Arrays.fill(heads, -1);
        vals = new int[m];
        nexts = new int[m];
        for (int i = 0; i < m; ++i) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            add(a, b);
        }
        System.out.println(bfs());
    }
}