AcWing 847. 图中点的层次-java
原题链接
简单
作者:
Astarion
,
2021-02-12 11:06:11
,
所有人可见
,
阅读 170
import java.io.*;
import java.util.*;
class Main {
static int n,m;
//稀疏图,邻接表存储
static int[] h = new int[100010];
static int[] e = new int[200020];
static int[] ne = new int[200020];
static int[] d = new int[200020];
static int idx;
static {
Arrays.fill(h,-1);
Arrays.fill(ne,-1);
}
//是否已确定距离
static boolean[] flag = new boolean[100010];
//广搜队列
static int head, tail;
static int[] queue = new int[100020];
//有向图插入
static void insert(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
//广搜求1->n距离
static int bfs() {
flag[1] = true;
queue[tail++] = 1;
d[1] = 0;
while (tail > head) {
int x = queue[head++];
if (x == n) return d[x];
for (int i = h[x]; i!=-1; i=ne[i]) {
if(!flag[e[i]]) {
flag[e[i]] = true;
queue[tail++] = e[i];
d[e[i]] = d[x]+1;
}
}
}
return -1;
}
public static void main(String[] args) throws IOException {
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader in = new BufferedReader(isr);
String[] strs = in.readLine().split(" ");
n = Integer.parseInt(strs[0]);
m = Integer.parseInt(strs[1]);
for (int i = 0; i<m; i++) {
strs = in.readLine().split(" ");
int a = Integer.parseInt(strs[0]);
int b = Integer.parseInt(strs[1]);
insert(a,b);
}
System.out.println(bfs());
in.close();
isr.close();
}
}