failed at the last two cases


  • 0
    C

    where did I do wrong? Please point it out, thanks.
    class Solution {
    public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
    build_graph(numCourses, prerequisites);
    vector<int> courses;
    for(unordered_map<int, unordered_set<int>>::iterator it = adjancey_list.begin(); it != adjancey_list.end(); it++){
    bool acyclic = dfs(it->first, courses);
    if(!acyclic)
    return vector<int>();
    }

    	for(int i=0; i<numCourses; i++){
    		if(color[i] == 0)
    			courses.insert(courses.begin(), i);
    	}	
    	return courses;
    }
    

    private:
    vector<int> color;
    unordered_map<int, unordered_set<int>> adjancey_list;
    void build_graph(int numCourses, vector<pair<int, int>>& prerequisites){
    for(int i=0; i<numCourses; i++)
    color.push_back(0); //paint white
    for(vector<pair<int, int>>::iterator it=prerequisites.begin(); it!= prerequisites.end(); it++)
    adjancey_list[it->second].insert(it->first);
    }
    bool dfs(int course, vector<int> &courses){
    if(color[course] == 0){
    color[course] = 1; //paint as grey
    unordered_set<int> children = adjancey_list[course];
    for(unordered_set<int>::iterator it=children.begin(); it!=children.end(); it++){
    bool acyclic = dfs(*it, courses);
    if(!acyclic)
    return false;
    }
    color[course] = 2;
    courses.insert(courses.begin(), course);
    }
    else if(color[course] == 1)
    return false;
    return true;
    }
    };


Log in to reply
 

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