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 ≤ 10^4. 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:

Given org = [1,2,3], seqs = [[1,2],[1,3]]
Return 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.

Given org = [1,2,3], seqs = [[1,2]]
Return false
Explanation:
The reconstructed sequence can only be [1,2].

Given org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Return true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Given org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Return true

Solution:

Count the indegree for each node,

Start with zero indegree node, and decrease its neighbors' indegree by one, then offer its zero indegree neighbors into the queue.

If there are not exact one zero indegree neighbor, return false.

Code:

public class Solution {
    /**
     * @param org a permutation of the integers from 1 to n
     * @param seqs a list of sequences
     * @return true if it can be reconstructed only one or false
     */

    class Node implements Comparable<Node> {
        int val;
        int indegree;
        ArrayList<Node> neighbors;
        public Node(int val) {
            this.val = val;
            indegree = 0;
            neighbors = new ArrayList<>();
        }
        public int compareTo(Node that) {
            return this.indegree - that.indegree;
        }
    }

    public boolean sequenceReconstruction(int[] org, int[][] seqs) {
        if (org == null || seqs == null) {
            return false;
        }
        if (org.length == 0 && seqs.length == 1 && seqs[0].length == 0) {
            return true;
        }
        if (seqs.length == 0 || seqs[0].length == 0) {
            return false;
        }
        Map<Integer, Node> map = constructGraph(seqs);
        Node root = null;
        int rootCount = 0;
        for (Map.Entry<Integer, Node> e : map.entrySet()) {
            if (e.getValue().indegree == 0) {
                root = e.getValue();
                rootCount++;
            }
        }
        if (rootCount != 1) {
            return false;
        }
        Queue<Node> q = new LinkedList<>();
        q.offer(root);

        int i = 0;
        while (!q.isEmpty()) {
            if (q.size() > 1) {
                return false;
            }
            Node node = q.poll();
            if (i >= org.length || node.val != org[i]) {
                return false;
            }

            for (Node n : node.neighbors) {
                n.indegree--;
                if (n.indegree == 0) {
                    q.offer(n);
                }
            }
            i++;
        }

        return i == org.length;
    }

    private Map<Integer, Node> constructGraph(int[][] seqs) {
        Map<Integer, Node> map = new HashMap<>();
        for (int i = 0; i < seqs.length; i++) { 
            for (int j = 0; j < seqs[i].length - 1; j++) {
                if (!map.containsKey(seqs[i][j])) {
                    map.put(seqs[i][j], new Node(seqs[i][j]));
                }
                if (!map.containsKey(seqs[i][j + 1])) {
                    map.put(seqs[i][j + 1], new Node(seqs[i][j + 1]));
                }
                map.get(seqs[i][j]).neighbors.add(map.get(seqs[i][j + 1]));
                map.get(seqs[i][j + 1]).indegree++;
            }
            if (!map.containsKey(seqs[i][seqs[i].length - 1])) {
                map.put(seqs[i][seqs[i].length - 1], new Node(seqs[i][seqs[i].length - 1]));
            }
        }
        return map;
    }
}