题解 | #公交车#

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    private static HashSet<Integer>[] adj;

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        while(in.hasNext()){
            solution(in);
        }
    }

    /**
     * 模拟法: bfs
     * @param in
     */
    private static void solution(Scanner in){
        // 公交站台数
        int n = in.nextInt();
        // 公交车数(线路数)
        int m = in.nextInt();
        // 为了降低构图复杂度, 每个公交车线路都建立一个虚拟节点, 使得公交车站之间只能通过虚拟节点相连接
        int V = n+m;

        // 构建图 点的范围[1:V]
        adj = new HashSet[V+1];
        for(int i=1; i<=V; i++){
            adj[i] = new HashSet<>();
        }
        int v,t;
        for(int i=1; i<=m; i++){
            t = in.nextInt();
            for(int j=1; j<=t; j++){
                v = in.nextInt();
                adj[n+i].add(v);
                adj[v].add(n+i);
            }
        }

        System.out.println(bfs(n));
    }

    /**
     * 广度优先搜索
     * @param terminal
     * @return
     */
    private static int bfs(int terminal){
        HashSet<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();

        visited.add(1);
        queue.offer(1);

        int dist = 0;
        int size;
        while(!queue.isEmpty()){
            Integer u;
            dist++;
            size = queue.size();
            for(int i=1; i<=size; i++){
                u = queue.poll();
                for(Integer v: adj[u]){
                    if(v == terminal){
                        return dist/2;
                    }
                    if(!visited.contains(v)){
                        visited.add(v);
                        queue.offer(v);
                    }
                }
            }
        }

        return -1;
    }
}