剑指offer115：重建序列

题目：
请判断原始的序列 org 是否可以从序列集 seqs 中唯一地 重建 。
序列 org 是 1 到 n 整数的排列，其中 1 ≤ n ≤ 104。重建 是指在序列集 seqs 中构建最短的公共超序列，即 seqs 中的任意序列都是该最短序列的子序列。
示例 1：
输入: org = [1,2,3], seqs = [[1,2],[1,3]]
输出: false
解释：[1,2,3] 不是可以被重建的唯一的序列，因为 [1,3,2] 也是一个合法的序列。
示例 2：
输入: org = [1,2,3], seqs = [[1,2]]
输出: false
解释：可以重建的序列只有 [1,2]。
示例 3：
输入: org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
输出: true
解释：序列 [1,2], [1,3] 和 [2,3] 可以被唯一地重建为原始的序列 [1,2,3]。
示例 4：
输入: org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
输出: true
分析：
广度优先搜索外加拓扑排序，广度优先要用到队列，如果队列中出现两个元素就证明org不是唯一的，所以队列最多只要求有一个元素，有向图以邻接表的形式用HashMap类型的graph保存，同时统计每个节点的入度并保存到另一个HashMap类型的inDefrees中。

代码：

package com.kuang;

import java.util.*;
import java.util.stream.Stream;

public class SequenceReconstruction {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegrees = new HashMap<>();
        for (List<Integer> seq: seqs){
            for (int num : seq) {
                if (num < 1 || num > org.length){
                    return false;
                }
                graph.putIfAbsent(num,new HashSet<>());
                inDegrees.putIfAbsent(num,0);
            }
            for (int i = 0; i < seq.size() - 1; i++) {
                int num1 = seq.get(i);
                int num2 = seq.get(i+1);
                if (!graph.get(num1).contains(num2)){
                    graph.get(num1).add(num2);
                    inDegrees.put(num2,inDegrees.get(num2)+1);
                }
            }
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int num : inDegrees.keySet()) {
            if (inDegrees.get(num) == 0){
                queue.add(num);
            }
        }
//        用来和org比较是否相等
        List<Integer> built = new LinkedList<>();
//        队列中元素如果数量大于1，就证明一定不是唯一的，返回false就完了
        while (queue.size() ==1){
            int num = queue.remove();
            built.add(num);
            for (int next : graph.get(num)){
                inDegrees.put(next,inDegrees.get(next)-1);
                if (inDegrees.get(next) == 0){
                    queue.add(next);
                }
            }
        }
        int[] result = built.stream().mapToInt(a -> a).toArray();
        return Arrays.equals(org,result);
    }
}