Check whether the original sequenceorgcan be uniquely reconstructed from the sequences inseqs. The org sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10^4. Reconstruction means building a shortest common supersequence of the sequences inseqs(i.e., a shortest sequence so that all sequences inseqsare subsequences of it). Determine whether there is only one sequence that can be reconstructed fromseqsand it is theorgsequence.

Have you met this question in a real interview?

Yes

Example

Given org = [1,2,3], seqs = [[1,2],[1,3]]
Return 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.

Given org = [1,2,3], seqs = [[1,2]]
Return false
Explanation:
The reconstructed sequence can only be [1,2].

Given org = [1,2,3], seqs = [[1,2],[1,3],[2,3]]
Return true
Explanation:
The sequences [1,2], [1,3], and [2,3] can uniquely reconstruct the original sequence [1,2,3].

Given org = [4,1,5,2,6,3], seqs = [[5,2,6,3],[4,1,5,2]]
Return true

class Solution {
public:
    /**
     * @param org a permutation of the integers from 1 to n
     * @param seqs a list of sequences
     * @return true if it can be reconstructed only one or false
     */
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        // Write your code here
        if (org.empty()) {
            return false;
        }
        map<int, set<int> > edges;
        map<int, int> d;  // indegree
        int n = org.size();
        for (int i : org) {
            edges[i] = set<int>();
            d[i] = 0;
        }

        for (auto& seq : seqs) {
            if (seq.empty()) {
                continue;
            }
            if (d.find(seq[0]) == d.end()) {
                return false;
            }
            for (int i = 1; i < seq.size(); ++i) {
                edges[i - 1].insert(seq[i]);
                ++d[i];
            }
        }
        queue<int> q;
        for (int i = 1; i <= n; ++i) {
            if (d[i] == 0) {
                q.push(i);
            }
        }
        int index = 0;
        while (q.size() == 1) {
            int cur = q.front(); q.pop();
            if (cur != org[index++]) {
                return false;
            }
            for (int j : edges[cur]) {
                --d[j];
                if (d[j] == 0) {
                    q.push(j);
                }
            }
        }
        return index == n;
    }
};