TLE graph topological sort solution, extension discussion and open for comments

• 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;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.