s4553711
6/16/2017 - 3:17 PM

207.cpp

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        if (!prerequisites.size()) return true;
        vector<vector<int> > map(numCourses, vector<int>());
        for(int i = 0; i < prerequisites.size(); i++) {
            map[prerequisites[i].first].push_back(prerequisites[i].second);
        }
        vector<bool> isVisited(numCourses, false);
        for(int j = 0; j < numCourses; j++) {
            if (!isVisited[j]) {
                vector<bool> onStack(numCourses, false);
                if (hasCycle(map, j, isVisited, onStack)) {
                    return false;
                }
            }
        }
        return true;
    }
    bool hasCycle(vector<vector<int> >& map, int j, vector<bool>& isVisited, vector<bool> &onStack) {
        isVisited[j] = true;
        onStack[j] = true;
        for(int k: map[j]) {
            if (onStack[k]) {
                return true;
            } else {
                if (hasCycle(map, k, isVisited, onStack)) {
                    return true;
                }
            }
        }
        onStack[j] = false;
        return false;
    }
};