时间戳

首页 > 解决方案 > 我的代码超过了时间限制。如何让我的代码更加优化？

java - 我的代码超过了时间限制。如何让我的代码更加优化？

问题描述

我的代码超过了测试用例 23 的时间限制。我使用 dfs 遍历了连接的房屋。我尽我所能从我身边进行优化。 Kattis 问题：我的互联网在哪里？

import java.util.Scanner;
import java.util.HashMap;
import java.util.ArrayList;

class Main{
    static boolean[] isVisited;
    static HashMap<Integer, ArrayList<Integer>> hashHouses;

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

        int numberOfHouses = scanner.nextInt();
        int numberOfCables = scanner.nextInt();

        hashHouses = new HashMap<>();

        for (int i = 1; i < numberOfHouses + 1; i++){
            hashHouses.put(i, new ArrayList<Integer>());
        }

        for (int i = 0; i < numberOfCables; i++){
            int x = scanner.nextInt();
            int y = scanner.nextInt();

            hashHouses.get(x).add(y);
            hashHouses.get(y).add(x);
        }

        isVisited = new boolean[numberOfHouses + 1];
        isVisited[1] = true;

        dfs(1);

        boolean isConnected = true;
        for (int i = 1; i < numberOfHouses + 1; i++){
            if (!isVisited[i]){
                System.out.println(i);
                isConnected = false;
            }
        }

        if (isConnected) System.out.println("Connected");
    }

    static void dfs(int start) {
        isVisited[start] = true;
        for (Integer i : hashHouses.get(start)) {
            if (!isVisited[i]) {
                dfs(i);
            }
        }
    }
}

标签： javadepth-first-searchbreadth-first-search

解决方案

问题不在您的算法中。只是Java的输入输出速度太慢了，这个在线判断。

解决方案是使用更高效的输入输出代码：

  • 对于输入，请使用自定义快速扫描仪。有关几个选项，请参阅此页面。
  • 对于输出，将结果写入 StringBuilder，然后将这个 StringBuilder 与单个System.out.

仅通过应用这两个优化，我就能够通过有关您问题的所有测试。

推荐阅读