Sequence Reconstruction

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

Example 1:

Input:
org: [1,2,3], seqs: [[1,2],[1,3]]

Output:
false

Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

Input:
org: [1,2,3], seqs: [[1,2]]

Output:
false

Explanation:
The reconstructed sequence can only be [1,2].

Example 3:

Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:
true

Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Example 4:

Input:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

Output:
true

There are couple solutions talking about topological sort. I don't think it's a correct one because a graph can have different results after a topological sort. For example, for ((1, 2), (1, 3)), the topological sort can lead to either 1, 2, 3 or 1, 3, 2. If your algorithm outputs 1, 3, 2 you may pass the test case, but it's not correct.

A better solution is this one, if it's prerequisite is correct. The idea is that all indices in the sequences should present in the original sequence and the order should be correct, i.e., index(seq[0]) < index(seq[1]). Then all consecutive indices in original sequence should have at least one consecutive sequence in the sequences.

public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        Map<integer, integer> orgIndices = new HashMap<>();
        boolean[] consecutive = new boolean[org.length];
        consecutive[org.length - 1] = true;
        for (int i = 0; i < org.length; i++) {
            orgIndices.put(org[i], i);
        }
        for (int[] seq : seqs) {
            if (!orgIndices.containsKey(seq[0]) || !orgIndices.containsKey(seq[1])) {
                return false;
            }
            if (orgIndices.get(seq[0]) >= orgIndices.get(seq[1])) {
                return false;
            }
            if (orgIndices.get(seq[0]) + 1 == orgIndices.get(seq[1])) {
                //n is one based, array is zero based
                consecutive[seq[0] - 1] = true;
            }
        }
        for (boolean isConsecutive : consecutive) {
            if (!isConsecutive) {
                return false;
            }
        }
        return true;
    }