Clean and Clear C++ O(n) Space O(n) Time BFS Topological Sort


  • 0
    F
    class Solution {
    public:
        bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
            unordered_map<int, vector<int>> dag;
            unordered_map<int, int> indegree;
            for (const auto & seq : seqs)
            {
                if (seq.size())
                    indegree[seq[0]];//make sure 0 is explicitly stored.
                for (int i = 0; i < (int)seq.size() - 1; ++ i)
                {
                    dag[seq[i]].push_back(seq[i + 1]);
                    indegree[seq[i + 1]]++;
                }
            }
            queue<int> numq;
            for (auto p : indegree)
                if (p.second == 0)
                    numq.push(p.first);
            int count = 0;
            while(!numq.empty())
            {
                int num = numq.front();
                numq.pop();
                if (!numq.empty() || num != org[count ++])
                    return false;
                for (auto n : dag[num])
                    if (--indegree[n] == 0)
                        numq.push(n);
            }
            if (count != indegree.size() || count != org.size())
                return false;
            return true;
        }
    };
    

Log in to reply
 

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