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

  • 1

    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;
        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
            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){
            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);

Log in to reply

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