Kattis where's my internet题Java DFS解法超时如何优化？

1. 输入读取效率过低 #

Java自带的Scanner类对大数据量输入的处理性能很差，Kattis第23个测试用例是房屋和线缆数量极大的边界用例，Scanner的输入解析速度跟不上就会触发超时。
优化方向：替换为BufferedReader配合StringTokenizer做输入读取，速度可提升数倍。

2. 邻接表存储结构冗余 #

你用HashMap<Integer, ArrayList<Integer>>存邻接表完全没有必要，本题房屋编号是1到numberOfHouses连续的正整数，直接用ArrayList<Integer>[]数组作为邻接表即可，省去HashMap的哈希计算、查找开销。

3. 递归DFS存在栈溢出风险 #

当房屋数量达到1e4以上时，递归DFS的调用深度过深会触发Java的栈溢出，也会表现为超时/运行错误。
优化方向：替换为迭代版DFS或者BFS（广度优先搜索），避免栈溢出问题。

4. 输出操作过于频繁 #

多次调用System.out.println打印未连接节点会产生大量IO开销，优化方向是用StringBuilder先拼接所有待输出内容，最后一次性打印。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Main{
    static boolean[] isVisited;
    static ArrayList<Integer>[] adj;

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

        // 用数组代替HashMap存邻接表，减少开销
        adj = new ArrayList[numberOfHouses + 1];
        for (int i = 1; i <= numberOfHouses; i++) {
            adj[i] = new ArrayList<>();
        }

        for (int i = 0; i < numberOfCables; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            adj[x].add(y);
            adj[y].add(x);
        }

        isVisited = new boolean[numberOfHouses + 1];
        // 用BFS代替递归DFS，避免栈溢出
        Queue<Integer> q = new LinkedList<>();
        q.add(1);
        isVisited[1] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            for (int next : adj[cur]) {
                if (!isVisited[next]) {
                    isVisited[next] = true;
                    q.add(next);
                }
            }
        }

        boolean isConnected = true;
        StringBuilder sb = new StringBuilder();
        // 先拼接所有输出内容，最后一次性打印
        for (int i = 1; i <= numberOfHouses; i++) {
            if (!isVisited[i]) {
                sb.append(i).append("\n");
                isConnected = false;
            }
        }
        if (isConnected) {
            System.out.println("Connected");
        } else {
            System.out.print(sb);
        }
    }
}

内容的提问来源于stack exchange，提问作者Iwfepoe Wmb Kcid