# 444 - Sequence Reconstruction

## 解法一 - Topological Sort

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();
}
};
``````