Быстрая топологическая сортировка, когда порядок узлов значителен?

Question

Я делаю this problem на Hackerrank. Краткое описание проблемы:

Вы пытаетесь восстановить последовательность из M различных целых чисел в диапазоне [1, 10^6]. Вам дано 1 < = N < = 10^3 подпоследовательности длины 2 < = K < = 10^3. Если возможны две последовательности, верните лексикографически меньшую.

Мой алгоритм выглядит следующим образом:

1. Создайте вершину для каждого отдельного целого. Храните их в хэш-карте.

2. Для каждой строки, если i предшествует j в строке, добавить ребро из i к j. Отслеживайте степень каждой вершины.

3. Сделать приоритетную очередь, ключ которой является значением каждой вершины. Завершите все вершины с неопределенностью 0.

4. Пока очередь непустая: поместите верхнюю вершину. Сократите зависимость каждого из своих детей.

Мои ответы верны, но я превысил лимит времени на больших тестовых шкафах. Я думаю, что приоритетная очередь является узким местом, но я не могу придумать способ сохранить вершины, отсортированные по значению менее чем O(log n). Мой код выглядит следующим образом, с классом Vertex исключены держать ее короче --- это в основном только добытчиками и сеттеров:

class FavoriteSequence { 
    private Map<Integer, Vertex> seen; 

    public void solve(int testNumber, Scanner in, PrintWriter out) { 
     int numRows = in.nextInt(); 
     seen = new HashMap<>(); 

     for (int i = 0; i < numRows; i++) { 
      int numInRow = in.nextInt(); 
      List<Vertex> row = IntStream.range(0, numInRow).mapToObj(x -> getVert(in.nextInt())).collect(
        Collectors.toList()); 

      int idx = 0; 
      for (Vertex v : row) { 
       v.incInDegree(idx); 
       v.addChildren(row.subList(++idx, numInRow)); 
      } 
     } 

     List<String> ans = new LinkedList<>(); 
     Queue<Vertex> bfsQ = new PriorityQueue<>(new Comparator<Vertex>() { 
      public int compare(Vertex o1, Vertex o2) { 
       int valCmp = Integer.compare(o1.getValue(), o2.getValue()); 
       return valCmp; 
      } 
     }); 

     bfsQ.addAll(seen.values().stream().filter(c -> c.getInDegree() == 0).collect(Collectors.toList())); 

     while (!bfsQ.isEmpty()) { 
      Vertex me = bfsQ.poll(); 
      ans.add(Integer.toString(me.getValue())); 

      for (List<Vertex> cs : me.getChildrens()) { 
       for (Vertex c : cs) { 
        if (c.decInDegree() == 0) { 
         bfsQ.add(c); 
        } 
       } 
      } 
     } 

     out.println(String.join(" ", ans)); 
    } 

    private Vertex getVert(int idx) { 
     Vertex me = seen.get(idx); 

     if (me == null) { 
      me = new Vertex(idx); 
      seen.put(idx, me); 
     } 

     return me; 
    } 
} 

Что я делаю слишком медленно? Я предоставил свой код ради того, чтобы сделать его конкретным, но я действительно ищу алгоритмический ответ.

Answer 1

Если я не ошибаюсь, этот код

 int idx = 0; 
     for (Vertex v : row) { 
      v.incInDegree(idx); 
      v.addChildren(row.subList(++idx, numInRow)); 
     } 

добавляет дуг, число которых растет квадратично с длиной подпоследовательности. Нужно только добавить дуги в транзитивной редукции, т. Е. От каждого элемента подпоследовательности к ее непосредственному преемнику.