剑指 Offer II 115：重建序列

题目

题目连接
给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。
检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。

例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。
如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。

示例 1：

输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。

示例 2：

输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。

示例 3：

输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。

解题

方法一：拓扑排序

参考链接
我们把sequences看成是一个有向图，若按照拓扑排序，入度为0的点只有一个，则一定是一个最短的超序列，否则不是。
此题也可以理解为，用sequences能不能转化为一个唯一序列。

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;

    }
};