AcWing 847. 图中点的层次
原题链接
简单
算法1
Java 代码
import java.util.*;
public class Main{
public static Scanner sc = new Scanner(System.in);
public static int N = (int)1e5 + 10;
public static int[] h = new int[N];
public static int[] e = new int[N];
public static int[] ne = new int[N];
public static int idx = 0;
public static int n,m;
public static int[] d = new int[N];//存储每个节点离起点的距离 d[1]=0
public static int[] q = new int[N];//存储层次遍历序列, 0号节点是编号为1的节点
public static void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
public static void main(String[] args){
n = sc.nextInt();
m = sc.nextInt();
//数组初始化
Arrays.fill(h, -1);
for(int i = 0; i < m; i++){
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
}
System.out.println(bfs(n));
}
public static int bfs(int n){
int head = 0;
int tail = -1;
q[++tail] = 1;
//数组初始化
Arrays.fill(d, -1);
d[1] = 0;
while(head <= tail){
int t = q[head++];//取出队列头部节点
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(d[j] == -1){
d[j] = d[t] + 1;//d[j]存储j节点离起点的距离,且可标记为访问过
q[++tail] = j;//把j结点压入队列
}
}
}
return d[n];
}
}
//改下标版本,可不参考
import java.util.*;
public class Main{
public static int N = (int)1e5 + 10;
public static int[] h = new int[N];
public static int[] e = new int[N];
public static int[] ne = new int[N];
public static int n, m;
public static int idx = 0;
public static Scanner sc = new Scanner(System.in);
public static int[] q = new int[N];
public static int[] d = new int[N];
public static void add(int a, int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
public static void main(String[] args){
n = sc.nextInt();
m = sc.nextInt();
Arrays.fill(h, -1);
for(int i = 0; i < m; i++){
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
}
System.out.println(bfs(n));
}
public static int bfs(int n){
int head = 0;
int tail = 0;
q[0] = 1;//0号节点是编号为1的节点
Arrays.fill(d, -1);
d[1] = 0;
while(head <= tail){
int t = q[head++];
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
if(d[j] == -1){
d[j] = d[t] + 1;
q[++tail] = j;
}
}
}
return d[n];
}
}