​LeetCode刷题实战444：序列重建

示例 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

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        int n=org.size();
        //统计序列集中的各个元素，保证所有的元素是唯一的1到n的数字
        vector<bool> signs(n+1,false);
        for(vector<int>& vec:seqs){//统计
            for(int&num:vec){
                if(num>n||num<=0){//保证不越界
                    return false;
                }
                signs[num]=true;
            }
        }
        for(int i=1;i<=n;++i){//判断元素的是否符合要求
            if(!signs[i]){
                return false;
            }
        }
        //建有向出度图和统计入度
        vector<vector<int>> graph(n+1);
        vector<int> indegree(n+1,0);
        for(vector<int>& vec:seqs){
            for(int i=0;i-1;++i){
                graph[vec[i]].push_back(vec[i+1]);
                ++indegree[vec[i+1]];
            }
        }
        //找出起始的结点
        queue<int> q;
        for(int i=1;i<=n;++i){
            if(indegree[i]==0){
                q.push(i);
            }
        }
        vector<int> res;//存储排序后的序列
        while(!q.empty()){
            if(q.size()>1){//保证只有一种序列
                return false;
            }
            //取出当前结点
            int cur=q.front();
            q.pop();
            res.push_back(cur);
            //更新相关的入读图
            for(int& num:graph[cur]){
                --indegree[num];
                if(indegree[num]==0){//统计新的起始点
                    q.push(num);
                }
            }
        }
        //先判断大小
        if(res.size()!=n){
            return false;
        }
        //再判断一致性
        return res==org;
    }
};