C++ topological sort using BFS


  • 0
    Z
    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;
        }
    };
    

Log in to reply
 

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