Description

Submission

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        map<int, set<int>> graph;
        vector<int> seq;
        int n = org.size();
        vector<int> inDegree(n + 1, 0);

        set<int> Set;
        for(auto& v: seqs) {
            for(auto x: v) {
                Set.insert(x);
            }
        }
        if(Set.size() != n) return false;
        auto it = Set.begin();
        for(int i = 1; i <= n; ++i, ++it) {
            if(*it != i) return false;
        }

        for(auto& v: seqs) {
            for(int i = 1; i < v.size(); ++i) {
                if(!graph[v[i-1]].count(v[i])) {
                    graph[v[i-1]].insert(v[i]);
                    ++inDegree[v[i]];
                }
            }
        }

        queue<int> q;
        vector<int> visited(n+1, 0);
        for(int i = 1; i <= n; ++i) {
            if(!inDegree[i]) q.push(i);
        }
        if(q.size() != 1) return false;
        while(!q.empty()) {
            int cur = q.front();
            q.pop();
            
            if(visited[cur]) continue;
            visited[cur] = 1;
            seq.push_back(cur);

            bool occured = false;
            for(auto x: graph[cur]) {
                if(visited[x]) continue;
                --inDegree[x];
                if(!inDegree[x]) {
                    q.push(x);
                    if(occured) return false;
                    occured = true;
                }
            }
        }

        if(seq.size() != n) return false;
        for(int i = 0; i < n; ++i) {
            if(seq[i] != org[i]) return false;
        }
        return true;
    }
};