Course Schedule Solutions in C++

// Source : https://leetcode.com/problems/course-schedule/
// Author : Hao Chen
// Date   : 2015-06-09




class Solution {
public:

    bool hasCycle(int n, vector<int>& explored, vector<int>& path, map<int, vector<int>>& graph) {
        
        for(int i=0; i<graph[n].size(); i++){
            
            //detect the cycle
            if ( path[graph[n][i]] ) return true;
            
            //set the marker
            path[graph[n][i]] = true;
            
            if (hasCycle(graph[n][i], explored, path, graph)) {
                return true;
            }
            //backtrace reset
            path[graph[n][i]] = false;
        }
        //no cycle found, mark this node can finished!
        explored[n] = true;
        return false;
        
    }

    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        
        //using map to stroe the graph, it's easy to search the edge for each node
        //the bool in pair means it is explored or not
        map<int, vector<int>> graph;
        for(int i=0; i<prerequisites.size(); i++){
            graph[prerequisites[i].first].push_back( prerequisites[i].second );
        }
        
        //explored[] is used to record the node already checked!
        vector<int> explored(numCourses, false);
        
        //path[] is used to check the cycle during DFS
        vector<int> path(numCourses, false);
        
        for(int i=0; i<numCourses; i++){
            
            if (explored[i]) continue;
            if (hasCycle(i, explored, path, graph)) return false;
            

        }
        return true;
    }
};

/// Source : https://leetcode.com/problems/course-schedule-ii/
/// Author : liuyubobobo
/// Time   : 2018-12-16

#include <iostream>
#include <vector>

using namespace std;


/// Check Directed Graph has circle
/// Time Complexity: O(m + n)
/// Space Complexity: O(m + n)
class Solution {

public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

        vector<vector<int>> g(numCourses);
        for(const pair<int, int>& p: prerequisites){
            int from = p.second;
            int to = p.first;
            g[from].push_back(to);
        }

        return hasCircle(g);
    }

private:
    bool hasCircle(const vector<vector<int>>& g){

        vector<bool> visited(g.size(), false);
        vector<bool> onPath(g.size(), false);
        for(int i = 0; i < g.size(); i ++)
            if(!visited[i])
                if(circleDFS(g, i, visited, onPath))
                    return true;
        return false;
    }

    bool circleDFS(const vector<vector<int>>& g, int v,
                   vector<bool>& visited, vector<bool>& onPath){

        visited[v] = true;
        onPath[v] = true;
        for(int next: g[v])
            if(!visited[next]){
                if(circleDFS(g, next, visited, onPath))
                    return true;
            }
            else if(onPath[next])
                return true;

        onPath[v] = false;
        return false;
    }
};


int main() {

    return 0;
}