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


  • 0
    T

    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(); 
        }
    };
    

Log in to reply
 

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