快速拓扑排序，当节点的顺序很重要时？

Question

我正在 this problem 关于 Hackerrank。问题总结为：

You are trying to reconstruct a sequence of M distinct integers in the range [1, 10^6]. You are given 1 <= N <= 10^3 subsequences of length 2 <= K <= 10^3. If two sequences are possible, return the one that is lexicographically smaller.

我的算法如下：

为每个不同的整数创建一个顶点。将它们存储在哈希映射中。
对于每一行，如果 i 在该行中出现在 j 之前，则添加一条从 i 到 j 的边。跟踪每个顶点的入度。
做一个优先队列，key为每个顶点的value。将入度为 0 的所有顶点入队。
当队列非空时：弹出顶部顶点。减少每个 children 的入度。

我的答案是正确的，但我在较大的测试用例上遇到了超出时间限制的问题。我认为优先级队列是瓶颈，但我想不出一种方法让顶点按值排序小于 O(log n)。我的代码如下，排除了 Vertex class 以使其更短 --- 它主要只是 getter 和 setter：

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

添加弧线，其数量随子序列的长度呈二次方增长。实际上只需要在传递归约中添加弧，即从子序列的每个元素到它的直接后继者。

快速拓扑排序，当节点的顺序很重要时？

Fast topological sort, when the order of nodes is significant?

java

algorithm

graph

topological-sort