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

Question

I'm doing this problem on Hackerrank. A summary of the problem is:

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.

My algorithm is as follows:

1. Create a vertex for each distinct integer. Store them in a hash map.

2. For each row, if i comes before j in the row, add an edge from i to j. Track the indegree of every vertex.

3. Make a priority queue, whose key is the value of each vertex. Enqueue all the vertices with indegree 0.

4. While the queue is nonempty: pop the top vertex. Decrement the indegree of each of its children.

My answers are correct, but I'm getting a time limit exceeded on the larger testcases. I think that the priority queue is the bottleneck, but I can't think of a way to keep the vertices sorted by value in less than O(log n). My code is as follows, with the Vertex class excluded to keep it shorter --- it's mostly just getters and setters:

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

What am I doing too slowly? I've provided my code for the sake of making it concrete, but I'm really looking for an algorithmic answer.

Answer 1

If I'm not mistaken, this code

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

adds arcs whose number grows quadratically with the length of the subsequence. It's really only necessary to add the arcs in the transitive reduction, i.e., from each element of the subsequence to its immediate successor.