C++ clean code for DFS solution with simple comments


  • 13
    L
    bool canFinish(int numCourses, vector<pair<int, int>>& prer) {
        vector<vector<int>> gragh(numCourses);
        vector<int> visited(numCourses, 0); // White at initialization
        for (int i = 0; i < prer.size(); i++) {
            gragh[prer[i].second].push_back(prer[i].first);
        }
        bool cycle = false;
        for (int i = 0; i < numCourses; i++) {
            if (cycle) return false;
            if (visited[i] == 0) dfs_top(i, gragh, visited, cycle);
        }
        return !cycle;
    }
    void dfs_top(int node, vector<vector<int>> &gragh, vector<int> &visited, bool &cycle) {
        if (visited[node] == 1) {cycle = true; return;} // cycle occurs, break the dfs chain and all return
        visited[node] = 1; //Gray, searching
        for (int i = 0; i < gragh[node].size(); i++) {
            dfs_top(gragh[node][i], gragh, visited, cycle);
            if (cycle) return; // do some pruning here
        }
        visited[node] = 2; //Black Once finished.
    }

  • 0
    G

    Consider this test case: numCourses is large, and the prerequisite dependency is like 0->1->2->3->4->.....->(n-1). IMO, the call stack will become too deep and cause issue.


  • 0
    G

    You are right. The algorithm can be changed as:

    class Solution{
        vector<vector<int>> vec;
        vector<int> visited;
        bool cycle;
    public:
        bool canFinish(int numCourses,vector<pair<int,int>> &prer){
    
            vector<int> vec2;
            for(int i=0;i<numCourses;i++){
                vec.push_back(vec2);
                visited.push_back(0);
            }
            for(int i=0;i<prer.size();i++)
                // vec[prer[i].second].push_back(prer[i].first);
                vec[prer[i].first].push_back(prer[i].second);
    
            cycle=0;
            
            for(int i=0;i<numCourses;i++){
                if(visited[i]==2)continue;
                else if(visited[i]==1)return false;
                // if(visited[i]==0)
                    dfs_fun(i);
                if(cycle==1)return false;
            }
            return true;
        }
        
        void dfs_fun(int i){
            if(visited[i]==1){cycle=1;return;}
            visited[i]=1;
            
            for(int j=0;j<vec[i].size();j++){
                int node=vec[i][j];
                if(visited[node]==0)
                    dfs_fun(node);
                else if(visited[node]==1){cycle=1;return;}
                else if(visited[node]==2)continue;
                if(cycle)return;//
            }
            visited[i]=2;
        }
    };

Log in to reply
 

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