C++ solution to Course Schedule 2


  • 0
    G
    class Solution{
        vector<vector<int>> vec;
        vector<int> visited;
        bool cycle;
        vector<int> path;
    public:
        vector<int> findOrder(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 vector<int>();
                // if(visited[i]==0)
                    dfs_fun(i);
                if(cycle==1)return vector<int>();
            }
            return path;
        }
        
        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;
            path.push_back(i);
        }
    };

Log in to reply
 

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