Maybe an easy understood answer with one travel at every course


  • 0
    X
    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<vector<int> > courseNeed(numCourses, vector<int>()); // pre-course map, [0][0] = 0 means that 0 doesn't need pre. [1][0] = 0 means that 1 needs 0   
            vector<int> res;  // result 
            bool visited[numCourses] = {false}; //ever visited or not
            //initialize
            for(int i=0; i<prerequisites.size(); i++){
                courseNeed[prerequisites[i].first].push_back(prerequisites[i].second);
            }
            for(int i=0; i<courseNeed.size(); i++){
                if(courseNeed[i].empty())
                    courseNeed[i].push_back(i);
            }
            // find the preCoures with one travel
            if( gene(res, courseNeed, visited) )
                return res;
            return vector<int>();
        }
        
        bool gene(vector<int> &res, vector<vector<int> > &courseNeed, bool visited[]){
            for(int i=0; i<courseNeed.size(); i++){
                if(visited[i])
                    continue;
                visited[i] = true;
                for(int j=0; j<courseNeed[i].size(); j++){
                    if(courseNeed[i][j] != i){
                        if( !find(res, courseNeed, courseNeed[i][j], visited) )
                            return false;
                        else
                            courseNeed[i][j] = i;
                    }
                }
                res.push_back(i);
            }
            return true;
        }
        
        bool find(vector<int> &res, vector<vector<int> > &courseNeed, int need, bool visited[]){
            if(visited[need]){
                if(courseNeed[need][0] == need)
                    return true;
                else
                    return false;
            }
            
            visited[need] = true;
            for(int i=0; i<courseNeed[need].size(); i++){
                if(courseNeed[need][i] != need){
                    if( !find(res, courseNeed, courseNeed[need][i], visited) )
                        return false;
                    else
                        courseNeed[need][i] = need;
                }
            }
            
            res.push_back(need);
            return true;
        }
    };

Log in to reply
 

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