C++ for Course Schedule 1


  • 0
    G

    Re: C++ clean code for DFS solution with simple comments

    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);
            cycle=0;
            
            for(int i=0;i<numCourses;i++){
                if(visited[i]==2)continue;
                else if(visited[i]==1)return false;
                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;
        }
    };

  • 0
    G

    explenation:

    vec[prer[i].second].push_back(prer[i].first);
    

    is the same result as :

    vec[prer[i].first].push_back(prer[i].second);

Log in to reply
 

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