3、有向图深搜

AcWing 847. 图中点的层次

树的数组单链表表示方法 dfs深搜

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.kuansou();
    }

    int n, m;
    int N = 200010;
    int[] e = new int[N];
    int[] ne = new int[N];
    int[] h = new int[N];//head指针
    int[] d = new int[N];
    Queue<Integer> queue = new LinkedTransferQueue();
    //e[h[a]]存储的是a的拉链头结点的结点值
    int idx = 1;

    void insert(int a, int b) {
        //将b点插到h[a]的后面
        //h[a]代表的是 a 这一点的head指针
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    int bfs() {
        d[1] = 0;
        queue.offer(1);
        while (!queue.isEmpty()) {
            int p = queue.poll();
            for (int i = h[p]; i != -1; i = ne[i]) {
                if(d[e[i]]==-1){
                    queue.offer(e[i]);
                    d[e[i]] = d[p] + 1;
                }
            }
        }
        return d[n];
    }

    void kuansou() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        Arrays.fill(d, -1);
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            insert(a, b);
        }
        System.out.println(bfs());
    }

}