Simple C++ DFS solution, Check Cycle at the same time


  • 1
    M

    When using the normal DFS method, it fails a lot times when there is a cycle in the graph. Here we use hashset to check cycle when we go through DFS.

    class Solution {
        vector<vector<int>> clist;
        vector<int> ans;
        unordered_set<int> vis;
        unordered_set<int> cyc;
        bool isCycle=false;
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            clist.assign(numCourses, vector<int>());
            for(int i=0; i<prerequisites.size(); i++)  //build pre course list
            {
                clist[prerequisites[i].second].push_back(prerequisites[i].first);
            }
            for(int j=0; j<numCourses; j++)
            {
                if(vis.count(j)<1) dfs(j);
                if(isCycle) return vector<int>();    
            }
            return ans;
        }
        void dfs(int j){
            cyc.insert(j);
            vis.insert(j);
            for(int k=0; k<clist[j].size(); k++)
            {
                if(cyc.count(clist[j][k])>0) isCycle=true;  //detect cycle at the same time
                if(vis.count(clist[j][k])<1) dfs(clist[j][k]);  //keep dfs
            }
            ans.insert(ans.begin(), j);
            cyc.erase(j);
        }
    };

Log in to reply
 

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