题解 | 【模板】单源最短路Ⅰ ‖ 无权图

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int s = Integer.parseInt(st.nextToken());

        int[] outDegree = new int[n + 1];
        List<int[]> edges = new ArrayList<>(m);

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            edges.add(new int[] {u, v});
            outDegree[u]++;
        }

        int[][] adj = new int[n + 1][];
        for (int u = 1; u <= n; u++) {
            adj[u] = new int[outDegree[u]];
        }

        int[] currentIndex = new int[n + 1];
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj[u][currentIndex[u]++] = v;
        }

        int[] dist = new int[n + 1];
        Arrays.fill(dist, -1);
        dist[s] = 0;

        int[] queue = new int[n];
        int front = 0, rear = 0;
        queue[rear++] = s;

        while (front < rear) {
            int u = queue[front++];
            for (int v : adj[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    queue[rear++] = v;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(dist[i]).append(' ');
        }
        System.out.println(sb.toString().trim());
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：使用BufferedReader和StringTokenizer高效读取输入数据。
2. 邻接表构建：第一次遍历边列表统计每个顶点的出度，第二次遍历填充邻接表数组，确保每个顶点的邻接点正确存储。
3. BFS实现：使用数组手动实现队列，避免使用Java集合框架中的队列结构以提高性能。从起点开始，逐层扩展，记录每个顶点的最短路径长度。
4. 结果输出：遍历距离数组，生成结果字符串并输出。