# C++ concise topological sort solution with comment

• Any suggestions will be appreciated

``````class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
if (seqs.size() == 0) return false;
int n = org.size(), count = 0;
unordered_map<int, unordered_set<int>> graph;   // record parents
vector<int> degree(n+1, 0); // record out degree
for (auto s : seqs) {   // build graph
for (int i = s.size()-1; i >= 0; --i) {
if (s[i] > n or s[i] < 0) return false; // in case number in seqs is out of range 1-n
if (i > 0 and !graph[s[i]].count(s[i-1])) {
graph[s[i]].insert(s[i-1]);
if (degree[s[i-1]]++ == 0) count ++;
}
}
}
if (count != n-1) return false; // all nodes should have degree larger than 0 except the last one
for (int i = n-1; i >= 0; --i) {    // topological sort
if (degree[org[i]] > 0) return false;   // the last node should have 0 degree
for (auto p : graph[org[i]])
if (--degree[p] == 0 and p != org[i-1]) // found a node that is not supposed to have 0 degree
return false;
}
return true;
}
};
``````

• Thanks for your code, very impressive.
Now your code cannot pass because of the newly added test case [1],[[],[]]
I add a little code to handle it.

``````class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
unordered_map<int, unordered_set<int>> graph;
vector<int> indegree(org.size() + 1);
int count = 0;

for (auto seq : seqs) {
for (int i = seq.size() - 1; i >= 0; --i) {
if (seq[i] < 1 || seq[i] > org.size()) return false;
if (i > 0 && graph[seq[i]].count(seq[i-1]) == 0) {
graph[seq[i]].insert(seq[i-1]);
if(indegree[seq[i-1]]++ == 0) count++;
}
if (i == 0 && graph.find(seq[i]) == graph.end()) {
graph.insert({seq[i], unordered_set<int>()});
}
}
}
if (graph.size() != org.size()) return false;
if (count != org.size() - 1) return false;
for (int i = org.size() - 1; i >= 0; --i) {
if (indegree[org[i]] != 0) return false;
for (auto neigh : graph[org[i]]) {
if (--indegree[neigh] == 0 && neigh != org[i-1]) return false;
}
}
return true;

}
};
``````

The core idea is to add all possible node into graph and then compare org's size with graph's size.

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