# C++ topological sort using BFS

• ``````class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
unordered_map<int,unordered_set<int> > edge;
unordered_map<int,int> indegree;
for(auto &e:seqs){    \\build the graph
if(e.size()==0)continue;
for(int i=0;i<e.size()-1;i++){
if(!indegree.count(e[i]))indegree[e[i]]=0;
if(edge[e[i]].count(e[i+1]))continue;
edge[e[i]].insert(e[i+1]);
indegree[e[i+1]]+=1;
}
if(!indegree.count(e.back()))indegree[e.back()]=0;
}
vector<int> res;
queue<int> indegree0;    \\find the start of topological sort
for(auto val:indegree){
if(val.second==0){
indegree0.push(val.first);
}
}
while(indegree.size()){       \\check whether the topological is unique
if(indegree0.size()!=1)return false;
int node = indegree0.front();
res.push_back(node);
indegree0.pop();
for(auto val:edge[node]){
indegree[val]-=1;
if(indegree[val]==0){
indegree0.push(val);
}
}
edge.erase(node);
indegree.erase(node);
}
return res==org;
}
};
``````

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