# 444 - Sequence Reconstruction

解法一 - Topological Sort

這題的重點在於，我們會不會在某些時刻發現 org 不唯一 or 不正確，例如：

1. 每次要從 sources 拿出下一個，會不會有好幾個選擇？（不唯一）

2. 每次要從 sources 拿出下一個，會不會跟 org 不合？（不正確）

剩下的實作就跟上面差不多。

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        // Init the graph
        unordered_map<int, int> inDegree;
        unordered_map<int, vector<int>> graph;
        for(auto& seq: seqs) {
            for(auto& num: seq) {
                inDegree[num] = 0;
                graph[num] = {};
            }
        }

        // Build the graph
        for(auto& seq: seqs) {
            if(seq.empty()) {
                continue;
            }

            for(int i = 0; i < seq.size() - 1; ++i) {
                int parent = seq[i];
                int child = seq[i + 1];
                ++inDegree[child];
                graph[parent].push_back(child);
            }
        }

        // If inDegree's size != org.size, that means there's not enough information        
        if(inDegree.size() != org.size()) {
            return false;
        }

        // Find sources
        queue<int> sources;
        for(auto& p: inDegree) {
            if(p.second == 0) {
                sources.push(p.first);
            } 
        }

        // Start topological sort
        // In each step, if source's size > 1 or sources.front() does not match org, it's wrong
        vector<int> order;
        while(!sources.empty()) {
            // If there are more than one choice at this time
            if(sources.size() > 1) {
                return false;
            }

            if(org[order.size()] != sources.front()) {
                return false;
            }

            int cur = sources.front();
            sources.pop();

            order.push_back(cur);

            for(auto& child: graph[cur]) {
                if(--inDegree[child] == 0) {
                    sources.push(child);
                }
            }
        }

        return order.size() == org.size();
    }
};