侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】图中点的层次

GabrielxD
2022-11-11 / 0 评论 / 0 点赞 / 20 阅读 / 577 字 / 正在检测是否收录...

题目

847. 图中点的层次


给定一个 nn 个点 mm 条边的有向图,图中可能存在重边和自环。

所有边的长度都是 11,点的编号为 1n1 \sim n

请你求出 11 号点到 nn 号点的最短距离,如果从 11 号点无法走到 nn 号点,输出 1-1

输入格式

第一行包含两个整数 nnmm

接下来 mm 行,每行包含两个整数 aabb,表示存在一条从 aa 走到 bb 的长度为 11 的边。

输出格式

输出一个整数,表示 11 号点到 nn 号点的最短距离。

数据范围

1n,m1051 \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());
    }
}

0

评论区