# c++ Simple and verbose solution using BFS and Topological sort

• I have used the idea that is used in the Alien Dictionary

``````class Solution {
public:
bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {

unordered_map<int,int> degree;
unordered_map<int,unordered_set<int>> valMap;
//Initialization
for (auto o:org)
valMap[o] = unordered_set<int>();

for (auto seq:seqs){
//If there is one element or the same element appears always first
//For example [[1]] or [[1,2],[1,3],[2,3]]
if (seq.size()>0 && !degree[seq[0]]);
for (int i = 1; i<seq.size();i++)
valMap[seq[i-1]].insert(seq[i]);
}

//generate the degree
for (auto valm:valMap)
for (auto val:valm.second){
//check is there any self loop
if (val == valm.first) return false;
degree[val]++;
}

if (degree.size()!=org.size()) return false;
//Get the first element into the queue
queue<int> iq;
for (auto d:degree){
if (d.second == 0){
if (iq.size()>0) return false;
iq.push(d.first);
}
}

//check the topological sort is possible or not
int count = 0;
while (!iq.empty()){
auto num = iq.front();
count++;
iq.pop();
for (auto val:valMap[num]){
if (!--degree[val]){
if (iq.size()>0) return false;
iq.push(val);
}
}
}

return count == org.size();
}
};
``````

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