C++ concise topological sort solution with comment


  • 7
    T

    Any suggestions will be appreciated

    class Solution {
    public:
        bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
            if (seqs.size() == 0) return false;
            int n = org.size(), count = 0;
            unordered_map<int, unordered_set<int>> graph;   // record parents
            vector<int> degree(n+1, 0); // record out degree
            for (auto s : seqs) {   // build graph
                for (int i = s.size()-1; i >= 0; --i) {
                    if (s[i] > n or s[i] < 0) return false; // in case number in seqs is out of range 1-n
                    if (i > 0 and !graph[s[i]].count(s[i-1])) {
                        graph[s[i]].insert(s[i-1]);
                        if (degree[s[i-1]]++ == 0) count ++;
                    }
                }
            }
            if (count != n-1) return false; // all nodes should have degree larger than 0 except the last one
            for (int i = n-1; i >= 0; --i) {    // topological sort
                if (degree[org[i]] > 0) return false;   // the last node should have 0 degree
                for (auto p : graph[org[i]]) 
                    if (--degree[p] == 0 and p != org[i-1]) // found a node that is not supposed to have 0 degree
                        return false;
            }
            return true;
        }
    };
    

  • 0
    Q

    Thanks for your code, very impressive.
    Now your code cannot pass because of the newly added test case [1],[[],[]]
    I add a little code to handle it.

    class Solution {
    public:
        bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
            unordered_map<int, unordered_set<int>> graph;
            vector<int> indegree(org.size() + 1);
            int count = 0;
    
            for (auto seq : seqs) {
                for (int i = seq.size() - 1; i >= 0; --i) {
                    if (seq[i] < 1 || seq[i] > org.size()) return false;
                    if (i > 0 && graph[seq[i]].count(seq[i-1]) == 0) {
                        graph[seq[i]].insert(seq[i-1]);
                        if(indegree[seq[i-1]]++ == 0) count++;
                    }
                    if (i == 0 && graph.find(seq[i]) == graph.end()) {
                        graph.insert({seq[i], unordered_set<int>()});
                    }
                }
            }
            if (graph.size() != org.size()) return false;
            if (count != org.size() - 1) return false;
            for (int i = org.size() - 1; i >= 0; --i) {
                if (indegree[org[i]] != 0) return false;
                for (auto neigh : graph[org[i]]) {
                    if (--indegree[neigh] == 0 && neigh != org[i-1]) return false;
                }
            }
            return true;
    
        }
    };
    

    The core idea is to add all possible node into graph and then compare org's size with graph's size.


Log in to reply
 

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