Sword finger offer II 115: reconstruction sequence

subject

Topic linking
Given a length of n Array of integers for nums , among nums Is in the range of [1,n] The arrangement of integers . One is also provided 2D An array of integers sequences , among sequences[i] yes nums The subsequence .
Check nums Is it the only shortest Supersequence . The shortest Supersequence yes The shortest length Sequence , And all sequences sequences[i] Are its subsequences . For a given array sequences , There may be multiple valid Supersequence .

for example , about sequences = [[1,2],[1,3]] , There are two shortest Supersequence ,[1,2,3] and [1,3,2] .
And for sequences = [[1,2],[1,3],[1,2,3]] , The only possible shortest Supersequence yes [1,2,3] .[1,2,3,4] Is a possible supersequence , But not the shortest .
If nums Is the only shortest sequence Supersequence , Then return to true , Otherwise return to false .
Subsequence One can delete some elements from another sequence or not delete any elements , A sequence that does not change the order of the remaining elements .

Example 1：

 Input ：nums = [1,2,3], sequences = [[1,2],[1,3]]
 Output ：false
 explain ： There are two possible supersequences ：[1,2,3] and [1,3,2].
 Sequence  [1,2]  yes [1,2,3] and [1,3,2] The subsequence .
 Sequence  [1,3]  yes [1,2,3] and [1,3,2] The subsequence .
 because  nums  Is not the only shortest supersequence , So back false.

Example 2：

 Input ：nums = [1,2,3], sequences = [[1,2]]
 Output ：false
 explain ： The shortest possible supersequence is  [1,2].
 Sequence  [1,2]  Is its subsequence ：[1,2].
 because  nums  Not the shortest supersequence , So back false.

Example 3：

 Input ：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
 Output ：true
 explain ： The shortest possible supersequence is [1,2,3].
 Sequence  [1,2]  It's a subsequence of it ：[1,2,3].
 Sequence  [1,3]  It's a subsequence of it ：[1,2,3].
 Sequence  [2,3]  It's a subsequence of it ：[1,2,3].
 because  nums  Is the only shortest supersequence , So back true.

Problem solving

Method 1 ： A topological sort

Reference link
We put sequences As a directed graph , If sorted by topology , The degree of 0 There is only one point , It must be the shortest supersequence , Otherwise, it's not .
This question can also be understood as , use sequences Can it be transformed into a unique sequence .

class Solution {
    
public:
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
    
        int n=nums.size();
        vector<vector<int>> g(n+1);
        vector<int> indeg(n+1);

        for(vector<int>& seq:sequences){
    
            for(int i=0;i<seq.size()-1;i++){
    
                int x=seq[i],y=seq[i+1];
                g[x].push_back(y);
                indeg[y]++;
            }
        }
        queue<int> q;
        for(int x=1;x<=n;x++){
    
            if(indeg[x]==0) q.push(x);
        }
        while(!q.empty()){
    
            if(q.size()>1) return false;
            int x=q.front();
            q.pop();
            for(int y:g[x]){
    
                if(--indeg[y]==0){
    
                    q.push(y);
                }
            }
        }
        return true;

    }
};