题目描述

Check whether the original sequence org can be uniquely reconstructed from the sequences in seqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 104. Reconstruction means building a shortest common supersequence of the sequences in seqs (i.e., a shortest sequence so that all sequences in seqs are subsequences of it). Determine whether there is only one sequence that can be reconstructed from seqs and it is the org sequence.

样例

Example 1:

Input:
org: [1,2,3], seqs: [[1,2],[1,3]]

Output:
false

Explanation:
[1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed.

Example 2:

Input:
org: [1,2,3], seqs: [[1,2]]

Output:
false

Explanation:
The reconstructed sequence can only be [1,2].

Example 3:

Input:
org: [1,2,3], seqs: [[1,2],[1,3],[2,3]]

Output:
true

Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Example 4:

Input:
org: [4,1,5,2,6,3], seqs: [[5,2,6,3],[4,1,5,2]]

Output:
true

算法1

(拓扑排序) $O(V+E)$

seq = [4,1,5,2]中，每个数字是一个vertex，连续的2个数字 4 -> 1 看做是图的边
只需要考虑连续的2个数字，因为 若 4->1, 1->5 成立，必有 4->5成立，所以不必考虑4->5了。

可重建 org seq，等价于: (1) topo 序列存在 (2) topo序列唯一 （3）topo序列等于org
topo序列唯一的条件是，BFS的过程中，queue的size一直是1，此时node出队列的顺序唯一。

注意：
corner case 1: [1], [] –> false；seq可能为空，所有degree都要初始化为-1，在seqs出现过再置0，最后有-1的degree则失败
corner case 2: [1], [[1], [1], [1]] –> true；seq可能长度为1，每个数字都要处理，不一定都能构成pair
corner case 3: [5,3,2,4,1], [[5,3,2,4],[4,1],[1],[3],[2,4], [1000000000], [-8, -9]]；每个数字的范围要检查。

C++ 代码

    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        int n = org.size();

        // node编号从1开始
        vector<int> degree(n+1, -1); // 若org里有的node在seqs中从未出现过，则build graph后依然是-1，可以被check出来。
        vector<vector<int>> graph(n+1); // adj list

        // WARN: seq的每个数字都要检查范围，并添加到degree中。
        // corner case 2 说明不必然总是成对添加
        // corner case 3 说明要处理1..n外的数字。

        for(const auto& seq : seqs) {
            for(int i=0; i<seq.size();i++) {
                int u = seq[i];
                if(u < 1 || u > n) return false; // 所有数字都要在1..n
                if(degree[u] == -1) degree[u] = 0;

                // 如果有下一个数，构成边
                if(i+1 < seq.size()) {
                    int v = seq[i+1];
                    if(v < 1 || v > n) return false; // 所有数字都要在1..n
                    if(degree[v] == -1) degree[v] = 0;

                    graph[u].push_back(v);
                    degree[v] ++;                    
                }
            }
        }

        queue<int> q;
        for(int i=1; i<=n; i++) {
            if(degree[i] == -1) return false; // org中有的node在seqs没有出现过
            if(degree[i] == 0) q.push(i);
        }

        vector<int> res;
        int nq = 0;
        while(q.size()) {
            if(q.size()!=1) return false;
            int u = q.front(); q.pop();
            nq ++;
            res.push_back(u);

            for(auto v : graph[u]) {
                degree[v] --;
                if(degree[v] == 0) q.push(v);
            }
        }

        if( nq != n || res != org) { return false; }

        return true;
    }