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

Solution

• 这是一道边界条件比较多的拓扑排序题，比如seqs里面的每个list大小为空；为1时虽然没有edge，但是这个letter就算成出现过了；seqs里面的list可能有完全重复的，所以要先判断在edge里面是不是存在；虽然org时1～n的，但是其中有些可能不会在seqs里面出现，所以要在遍历seqs的时候才init in map和edges map。
• 判断的时候除了不足org的长度会返回false，还有edges的有些成员有环，所以没有在output中出现的情况会返回false

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Integer> in = new HashMap<Integer, Integer>();
        Map<Integer, Set<Integer>> edges = new HashMap<Integer, Set<Integer>>();
        for (List<Integer> seq : seqs) {
            if (seq.size() == 1) {
                int num = seq.get(0);
                if (! edges.containsKey(num)) {
                    edges.put(num, new HashSet<Integer>());
                    in.put(num, 0);
                }
                continue;
            }
            for (int i=0; i<seq.size()-1; i++) {
                if (! edges.containsKey(seq.get(i))) {
                    edges.put(seq.get(i), new HashSet<Integer>());
                    in.put(seq.get(i), 0);
                }
                if (! edges.containsKey(seq.get(i+1))) {
                    edges.put(seq.get(i+1), new HashSet<Integer>());
                    in.put(seq.get(i+1), 0);
                }
                if (edges.get(seq.get(i)).add(seq.get(i+1))) {
                    in.put(seq.get(i+1), in.get(seq.get(i+1)) + 1);
                }
            }
        }
        Queue<Integer> q = new LinkedList<Integer>();
        for (int key: in.keySet()) {
            if (in.get(key) == 0) {
                q.offer(key);
            }
        }
        int ptr = 0;
        while (! q.isEmpty()) {
            if (q.size() != 1 || org.length == ptr) return false;
            int index = q.poll();
            //System.out.println(index);
            if (org[ptr ++] != index) return false;
            if (! edges.containsKey(index)) return false;
            for (int outNum : edges.get(index)) {
                int tmp = in.get(outNum) - 1;
                if (tmp == 0) {
                    q.offer(outNum);
                }
                else {
                    in.put(outNum, tmp);
                }
            }
        }
        return ptr == org.length && ptr == edges.size();
    }
}