HackerRackの道路と図書館のタイムアウト

Question

私はこのHackerRankの問題に取り組んできましたが、大きな入力サイズのためにコードがタイムアウトしている理由を理解できないようです。私は、時間を短縮するためにハッシュマップとして隣接リストを実装しました。また、実行時間を最適化するための標準として、DFSにスタックを使用しています。私の基本的な戦略は、DFSを使用して接続されたノードのグループを削除し、残りのものがなくなるまで（DFSでノードが削除されるまで）それを継続することです。問題は一般的にグラフあたり80,000個の切断された部分があることです。私は隣人のない単一のノードを取り出します（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; 
    } 

参考までに、約2MBのファイル入力で私のコードを実行するのに約1.5秒かかります。

Answer 1

、近く、何をやっている：

この

は Roads and Libraries challenge on HackerRankのすべてのテストに合格します。 しかし、 exploredリストを保持し、隣接マップから削除すると、 numDisconnectedと depthFirstSearch（以前のバージョンの質問）で冗長な作業を行っています。どちらも、深さの最初の検索を実装するのに十分なはずです。

exploredをブール値[]に変更し、それを使用して切断されたコンポーネントを探索し、コンポーネントが完了したときにDFSを開始する次のノードを見つけるために、adjから取り除かずにアルゴリズムを調整しました。

接続されていないノードを削除する前処理ステップは不要です。

Answer 2

（この質問の最初のリビジョンに）あなたの元のコードから始めて、私は、ArrayList秒でそれらのHashMap Sを置き換えexploredためHashSetを使用し、depthFirstSearch（単に簡略化のためではなく、パフォーマンス）をインライン化し、処分しました早すぎる最適化（隣人のないノードの削除、メインループでの早期復帰）のように感じるカップルステップ。 HashMap<Integer, List<Integer>>は、この作業のために良いデータ構造であり、一般的に

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)); 
     } 
    } 
}