Natually, I was trying to create a directed graph and do a topological sort to reconstruct the original sequence while comparing with the given `org`

sequence whenever a unique zero-indegree node can be found. However, I got TLE because later I saw the optimized solution should have `O(N+sum_i L_i)`

time, where `L_i`

is the length of given `seqs[i]`

.

Then I checked my graph solution, which costs `O(N+sum_i L_i)`

time alone to create the graph and uses another `O(N^2)`

time to do topological sort. So I guess this is why I got TLE (?).

Finally, I am wondering how the optimized solution could achieve just in linear time. It is probably because that the original sequence is also given as a reference. If only `vector<vector<int>> seqs`

is given to ask to restore a shortest possible (no duplicate) original sequence, I guess the problem will be much more difficult and probably cost more time, isn't it? Any comment is appreciated!

```
unordered_map<int, unordered_set<int>> out; // out neighbors
unordered_map<int, int> indeg; // in degree (count of in-neighbors)
void getGraph(vector<int>& org, vector<vector<int>>& seqs) {
for (int x:org) indeg[x] = 0;
for (auto& seq : seqs) {
int n = seq.size();
for (int i = 1; i < n; ++i) {
auto res = out[seq[i-1]].insert(seq[i]); if (res.second) indeg[seq[i]]++;
}
}
}
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
if (org.empty() != seqs.empty()) return false;
getGraph(org, seqs);
int counter = 0;
while (!indeg.empty()) {
bool found = false;
for (auto& x:indeg) {
if (x.second) continue;
if (!found && x.first == org[counter]) { found = true; }
else return false;
}
if (found) {
for (auto& nb:out[org[counter]]) indeg[nb]--;
out.erase(org[counter]);
indeg.erase(org[counter]);
counter++;
}
else return false;
}
return true;
}
```