207. Course Schedule

解題思路

感覺只是把 neetcode 的解法寫成 C++ 版本而已，改天要再練習一次。

程式碼

class Solution {
public:
    map<int, set<int>> preMap;
    set<int> checkCycle;
    bool dfs(int currentCourse)
    {
        if(checkCycle.find(currentCourse) != checkCycle.end()) // alreadly visited
            return false;
        if(preMap[currentCourse].empty()) // no prerequisites or are all valid
            return true;
        
        checkCycle.insert(currentCourse);
        for(auto c : preMap[currentCourse])
        {
            if(!dfs(c))
                return false;
        }
        checkCycle.erase(currentCourse);
        preMap[currentCourse].clear();
        return true;
    }
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        for(int i=0; i<prerequisites.size(); i++)
            preMap[prerequisites[i][0]].insert(prerequisites[i][1]);
        
        for(int i=0; i<numCourses; i++)
        {
            if(!dfs(i))
                return false;
        }
        return true;
    }
};