AcWing 847. 图中点的层次
原题链接
简单
作者:
huaqingren
,
2021-02-08 20:43:51
,
所有人可见
,
阅读 201
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
public class Main
{
private static int N=100010;
private static boolean[] st=new boolean[N];
private static List<Integer>[] list;
private static Map<Integer,Integer> map=new HashMap<>();//map.put(2,1)表示1号点走到2号点步长为1
private static int n;
private static int m;
public static void main(String[] args)
{
Scanner scan=new Scanner(System.in);
n=scan.nextInt();
m=scan.nextInt();
//邻接表
list=new ArrayList[N];
for(int i=1;i<=n;i++)
list[i]=new ArrayList<>();
for(int i=0;i<m;i++)
{
int a=scan.nextInt();
int b=scan.nextInt();
list[a].add(b);
}
System.out.println(bfs());
scan.close();
}
private static int bfs()
{
st[1]=true;
map.put(1,0);
Queue<Integer> queue=new LinkedList<>();
queue.offer(1);
while(!queue.isEmpty())
{
int t=queue.poll();
int dis=map.get(t);
if(t==n)
return dis;
for(int i=0;i<list[t].size();i++)
{
int s=list[t].get(i);
if(st[s]) continue;
st[s]=true;
queue.offer(s);
map.put(s, dis+1);
}
}
return -1;
}
}