【月度刷题计划同款】结合拓扑排序的构造题

输入：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。

输入：nums = [1,2,3], sequences = [[1,2]]

输出：false

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

输入：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。

class Solution {
    int N = 10010, M = N, idx;
    int[] he = new int[N], e = new int[M], ne = new int[M], in = new int[N];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx++;
        in[b]++;
    }
    public boolean sequenceReconstruction(int[] nums, int[][] ss) {
        int n = nums.length;
        Arrays.fill(he, -1);
        for (int[] s : ss) {
            for (int i = 1; i  d = new ArrayDeque();
        for (int i = 1; i 

const N = 10010, M = N
const he: number[] = new Array(N).fill(-1), e = new Array(N).fill(0), ne = new Array(N).fill(0), ind = new Array(N).fill(0);
let idx = 0
function add(a: number, b: number): void {
    e[idx] = b
    ne[idx] = he[a]
    he[a] = idx++
    ind[b]++
}
function sequenceReconstruction(nums: number[], ss: number[][]): boolean {
    he.fill(-1); ind.fill(0)
    idx = 0
    const n = nums.length
    for (const s of ss) {
        for (let i = 1; i ()
    let head = 0, tail = 0
    for (let i = 1; i  1) return false
        const t = stk[head++]
        if (nums[loc++] != t) return false
        for (let i = he[t]; i != -1; i = ne[i]) {
            const j = e[i]
            if (--ind[j] == 0) stk[tail++] = j
        }
    }
    return true
};