题解 | #公交车#bfs模拟

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static List<List<Integer>> graph;  // 存放的是每个公交车经过的站台列表
    static List<List<Integer>> zhanTai; // 存放的是每个站台有哪些公交车经过
    static boolean[] visited;  // 用于标记每个站台是否访问过
    static boolean[] used;     // 用于标记每个公交车是否使用过
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            graph = new ArrayList<>();
            zhanTai = new ArrayList<>();
            visited = new boolean[n + 1];
            used = new boolean[m + 1];
            for (int i = 0; i <= m; i++) {
                graph.add(new ArrayList<>());
            }
            for (int i = 0; i <= n; i++) {
                zhanTai.add(new ArrayList<>());
            }
            for (int i = 1; i <= m; i++) {
                int k = sc.nextInt();
                for (int j = 0; j < k; j++) {
                    graph.get(i).add(sc.nextInt());
                }
            }
            // System.out.println(graph);
            for (int i = 0; i < graph.size(); i++) {
                if (!graph.get(i).isEmpty()) {
                    for (Integer integer : graph.get(i)) {
                        zhanTai.get(integer).add(i);
                    }
                }
            }
            // System.out.println(zhanTai);
            //存放每个站台的公交车
            ArrayDeque<int[]> queue = new ArrayDeque<>();
            //这个是站台1的公交车
            for (Integer bus : zhanTai.get(1)) {
                queue.add(new int[] {1, bus});
            }
            int cost = 0;
            while (!queue.isEmpty()) {
                int size = queue.size();
                cost++;
                while (size-- > 0) {
                    int[] temp = queue.poll();
                    int busTai = temp[0];//拿到当前站台
                    int bus = temp[1];//拿到当前站台对应公交车
                    if (used[bus]) continue;
                    used[bus] = true;//记录公交车已坐过
                    List<Integer> zhanTaiS = graph.get(bus);//拿到这个公交车经过的站台
                    for (Integer tai : zhanTaiS) {
                        if (tai == n) {//如果能到达就直接返回
                            System.out.println(cost);
                            return;
                        }
                    }
                    visited[busTai] = true; // 标记当前站台为已访问
                     // 对于该公交车经过的每个站台，获取该站台的所有公交车并加入队列
                    for (Integer tai : zhanTaiS) {
                        if (!visited[tai]) { // 如果该站台未被访问过
                            for (Integer car : zhanTai.get(tai)) {
                                queue.add(new int[] {tai, car}); // 将新的{站台, 公交车}加入队列
                            }
                        }
                    }
                }
            }
            System.out.println(-1);
        }
    }
}