HackerRank 上的道路和图书馆超时

Question

我研究这个 HackerRank 问题已经有一段时间了，我似乎无法理解为什么我的代码会在大输入量时超时。我已经将邻接列表实现为哈希映射以减少时间，并且一直在为我的 DFS 使用堆栈，这是优化它的运行时间的标准。我这里的基本策略是使用 DFS 删除一组连接的节点，并继续这样做直到剩下 none（我的 DFS 在到达时删除节点），问题是通常有 ~80,000 个断开连接的部分每个图 after 我取出没有邻居的单个节点（因此 DFS 被调用 80,000 次）。这里有什么特别好的策略吗？

  static int numDisconnected(HashMap<Integer, List<Integer>> adj)  {
    int result = 0;
    List<Integer> iter = new ArrayList<>(adj.keySet());
    for (int k : iter) {
      if (adj.get(k).size() == 0)  {
        adj.remove(k);
        result++;
      }
    }
    HashMap<Integer,Boolean> explored = new HashMap<>();
    for (int i : adj.keySet())  {
      explored.put(i,false);
    }
    while (!adj.keySet().isEmpty())  {
      result++;
      depthFirstSearch(adj,explored);
    }
    return result;
  }

作为参考，我的代码在我的机器上运行大约需要 1.5 秒来输入 ~2MB 文件。

Answer 1

从你的原始代码开始（在这个问题的第一次修订中），我用 ArrayLists 替换了那些 HashMaps，用 HashSet 代替 explored , 内联 depthFirstSearch （只是为了简单，而不是为了性能），并摆脱了几个感觉像过早优化的步骤（删除没有邻居的节点，在主循环中提前 return）。

这通过了 Roads and Libraries challenge on HackerRank 中的所有测试：

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

public class Solution {
    static long cost(long cLib, long cRoad, ArrayList<List<Integer>> g, int gSize)  {
        if (cLib <= cRoad)  {
            return cLib * (long)gSize;
        }
        int discon = numDisconnected(g);
        return (cRoad * (gSize - discon)) + (cLib * discon);
    }

    static int numDisconnected(ArrayList<List<Integer>> adj)  {
        int result = 0;
        HashSet<Integer> explored = new HashSet<>();
        int length = adj.size();
        for (int i = 0; i < length; i++) {
            if (!explored.contains(i)) {
                Stack<Integer> stack = new Stack<>();
                stack.push(i);
                while (!stack.empty()) {
                    int curr = stack.pop();
                    explored.add(curr);
                    for (int neighbor : adj.get(curr)) {
                        if (!explored.contains(neighbor)) {
                            stack.push(neighbor);
                        }
                    }
                }

                result += 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int a0 = 0; a0 < q; a0++){
            int nCities = in.nextInt();
            ArrayList<List<Integer>> adj = new ArrayList<List<Integer>>(nCities);
            for (int i = 0; i < nCities; i++) {
                adj.add(new ArrayList<Integer>());
            }
            int nRoads = in.nextInt();
            long cLib = in.nextLong();
            long cRoad = in.nextLong();
            for (int i = 0; i < nRoads; i++) {
                int city_1 = in.nextInt() - 1;
                int city_2 = in.nextInt() - 1;
                adj.get(city_1).add(city_2);
                adj.get(city_2).add(city_1);
            }
            System.out.println(cost(cLib, cRoad, adj, nCities));
        }
    }
}

Answer 2

一般来说，您正在做的事情很接近，HashMap<Integer, List<Integer>> 是适合此任务的良好数据结构。但是你通过保留 explored 列表并从 numDisconnected 和 depthFirstSearch 中的邻接图中删除（在你的问题的早期版本中）来做多余的工作。这些中的任何一个都应该足以实现深度优先搜索。

我调整了你的算法，不从 adj 中删除，将 explored 更改为 boolean[] 并使用它来探索断开连接的组件，并找到下一个节点以在组件完成时启动 DFS .

通过了，不需要去除未连接节点的预处理步骤

（抱歉，我只是改述而不是发布代码，但我不想破坏它）

HackerRank 上的道路和图书馆超时

Time out in Roads and Libraries on HackerRack

java

algorithm

graph

graph-algorithm