---
tags: leetcode
---

# [444. Sequence Reconstruction](https://leetcode.com/problems/sequence-reconstruction/)
---
# My Solution
## The Key Idea for Solving This Coding Question
* Determine whether the graph have a unique topological sort.
* For a curr node, after we decrement the indegrees of all its neighbors, if there are more than one neighbor has zero indegree, the topological sort is not unique.
## C++ Code

class Solution {
public:
    bool sequenceReconstruction(vector<int> &nums, vector<vector<int>> &sequences) {
        unordered_map<int, unordered_set<int>> graph;
        unordered_map<int, int> indegree;
        for (auto &seq : sequences) {
            if (seq.size() == 1) {
                auto iter1 = indegree.find(seq[0]);
                if (iter1 == indegree.end()) {
                    indegree[seq[0]] = 0;
                }

                auto iter2 = graph.find(seq[0]);
                if (iter2 == graph.end()) {
                    graph.insert({seq[0], {}});
                }
                continue;
            }

            for (int i = 0; i + 1 < seq.size(); ++i) {
                auto indegreeIter = indegree.find(seq[i]);
                if (indegreeIter == indegree.end()) {
                    indegree[seq[i]] = 0;
                }

                auto uIter = graph.find(seq[i]);
                if (uIter == graph.end()) {
                    graph[seq[i]].insert(seq[i + 1]);
                    ++indegree[seq[i + 1]];
                    continue;
                }

                auto vIter = uIter->second.find(seq[i + 1]);
                if (vIter == uIter->second.end()) {
                    uIter->second.insert(seq[i + 1]);
                    ++indegree[seq[i + 1]];
                }
            }
        }

        int zeroCnt = 0;
        vector<int> superSeq;
        queue<int> q;
        for (auto &x : indegree) {
            if (x.second == 0) {
                q.push(x.first);
                superSeq.push_back(x.first);
                ++zeroCnt;
                if (zeroCnt > 1) {
                    return false;
                }
            }
        }

        while (!q.empty()) {
            int curr = q.front();
            q.pop();

            zeroCnt = 0;
            for (auto &next : graph[curr]) {
                --indegree[next];
                if (indegree[next] == 0) {
                    q.push(next);
                    superSeq.push_back(next);
                    ++zeroCnt;
                    if (zeroCnt > 1) {
                        return false;
                    }
                }
            }
        }

        return superSeq == nums;
    }
};

## Time Complexity
## Space Complexity
# Miscellaneous
<!--
# Test Cases

[1,2,3]
[[1,2],[1,3]]

[1,2,3]
[[1,2]]

[1,2,3]
[[1,2],[1,3],[2,3]]

* Wrong Answer

[1]
[[1]]

* Wrong Answer

[1,4,2,3]
[[1,2],[1,3],[2,3],[4,2]]

* Wrong Answer

[1,2,3,4,5]
[[1,2,3,4,5],[1,2,3,4],[1,2,3],[1],[4],[5]]

* Wrong Answer

[1,2,3]
[[1,3],[1,2]]

-->