?LeetCode刷題實戰(zhàn)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();
????????//統(tǒng)計序列集中的各個元素，保證所有的元素是唯一的1到n的數字
????????vector<bool> signs(n+1,false);
????????for(vector<int>& vec:seqs){//統(tǒng)計
????????????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;
????????????}
????????}
????????//建有向出度圖和統(tǒng)計入度
????????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){//統(tǒng)計新的起始點
????????????????????q.push(num);
????????????????}
????????????}
????????}
????????//先判斷大小
????????if(res.size()!=n){
????????????return?false;
????????}
????????//再判斷一致性
????????return?res==org;
????}
};