Naive c++ solution using dfs


  • 0
    R
    class Solution {
    public:
        struct course
        {
            int num;
            bool global_visited, local_visited;
            vector<course*> prereq;
            course():global_visited(false), local_visited(false) {}
        };
        bool hasCycle(course* start)
        {
            for(int i = 0; i < start->prereq.size();)
            {
                (start->prereq)[i]->global_visited = true;
                if(!(start->prereq)[i]->local_visited)
        		{
        			(start->prereq)[i]->local_visited = true;
        			if(hasCycle((start->prereq)[i]))
        			    return true;
        			(start->prereq)[i]->local_visited = false;
        			i++;
        		}
        		else
        		    return true;
            }
            return false;
        }
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
        {
            if(numCourses <= 1) return true;
            vector<course> courses(numCourses);
            for(int i = 0; i < numCourses; ++i)
               courses[i].num = i;
            for(int i = 0; i < prerequisites.size(); ++i)
                courses[prerequisites[i].front()].prereq.push_back(&courses[prerequisites[i].back()]); 
            
            for(int i = 0; i < numCourses; ++i) {
                if(!courses[i].global_visited)
                {
                    courses[i].local_visited = true;
                    if(hasCycle(&courses[i])) return false;
                    courses[i].local_visited = false;
                }
            }
            return true;
        }
    };

Log in to reply
 

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