C++ DFS topological sort solution.


  • 0
    H

    class Solution {
    public:

    vector<int> findOrder(int numCourses, vector<pair<int, int> > & prerequisites) {
        // use dfs topological sort
        vector<int> ans;
        if (numCourses == 0) return ans;
        if (numCourses == 1) return vector<int>(1,0);
    
        // preprocess the graph into a non-duplicate edge list
        vector<vector<int> > edge(numCourses, vector<int>());
        vector<set<int> > uedge(numCourses, set<int>());
        for(auto pre : prerequisites){
            uedge[pre.first].insert(pre.second);
        }
        for(int i=0; i<numCourses; ++i){
            edge[i].insert(edge[i].end(), uedge[i].begin(), uedge[i].end());
        }
        uedge.clear();
        
        // do a graph depth first search topological sort
        vector<bool> vis(numCourses, false);// visited means the node has been explored
        stack<int> dfs_s, path;
        unordered_set<int> on_path;
        for (int i=0; i<numCourses; ++i){
            if (vis[i]) continue;
            dfs_s.push(i);
            while(!dfs_s.empty()){
                int cur = dfs_s.top();
                vis[cur] = true;
                path.push(cur);
                on_path.insert(cur);
                int ct = 0;
                for(auto e : edge[cur]){
                    if (on_path.find(e) != on_path.end()){
                        return vector<int>(); // this is a path with cycle
                    }
                    if (vis[e]) continue;
                    dfs_s.push(e);
                    ++ct;
                }
                if (ct == 0){// end of current path
                    while (!path.empty() && path.top() == dfs_s.top()){
                        int t = path.top();
                        ans.push_back(t);
                        on_path.erase(t);
                        path.pop();
                        dfs_s.pop();
                    }
                }
            }
        }
        return ans;
    }
    

    };


Log in to reply
 

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