前言

今天選擇的是TOP 100 LIKED的另外一題~207. Course Schedule，牽涉到一個經典的演算法，一起來看看吧！

想法

這題的題目是給了一堆課的先修要求，然後要檢查是否可以在不違反這些先修課要求的條件下完成它。
而這題首要之務就是先轉換題目成比較可以使用的格式，因此我想：先把修課要求存成map，如下：

// for every course, record the course that would study after that
unordered_map<int, vector<int>> preCourseRev;
for(int i=0;i<prerequisites.size();++i){
    preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
}

然後我就卡住了，一開始的判斷想說這題應該是要看有沒有出現死結，所以就針對每一堂課，去追溯他的先修課，DFS去追每一堂課的前面，直到出現重複的。然後就TLE了XD：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // record the prerequisites first
        map<int, vector<int>> preCourse;
        for(int i=0;i<prerequisites.size();++i){
            preCourse[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        // keep record to required courses
        vector<int> seen(numCourses, 0);
        //int checked[numCourses]={0};
        
        
        // check for every courses
        for(int i=0;i<numCourses;++i){
            seen={0};

            // if not checked yet
            //if(checked[i]==0){
                // trace to see if prerequisites conflict
                //seen[i] = 1;
                //for(int j : preCourse[i]){
            if(checkForCourse(i, seen, preCourse)==false){
                return false;
            }
       // }
            //}
        }
        return true;
    }
    bool checkForCourse(int i, vector<int> &seen,map<int, vector<int>> &preCourse){
        if(seen[i]==1){
            return false;
        }
                

        else{
            seen[i]=1;
            for(int j: preCourse[i]){
                if(checkForCourse(j, seen, preCourse)==false){
                        return false;
                }
            }
            seen[i]=0;
            //checked[i]==1;
            return true;
        }
    }
};

檢討結果是我這樣重複得計算搞得太多，等於每堂課分岔再分岔去它前面修過的課，針對每次修過的課又檢查好幾次，其實每次應該檢查自己就好了。
不過其實這題應用的是這個重點─Topological sort演算法，可以參考這邊提供的說明Topological Ordering。
整個演算法的重點就是：

• 前置作業─課堂計算

1. 同前面所說，先轉換成每一堂課的map
2. 計算每堂課有幾門先修課
3. 計算有幾堂課沒有先修課，那就是接下來可以作為第一堂課的課，我們把它存在一個queue裡

• 遍歷每一堂課
  現在我們要來排序了，我們總共要修n堂課，所以會遍歷n堂，而起點就應該是沒有先修課的一堂課

4. 如果還沒遍歷完n堂課，但卻每堂課都有先修課，代表其中有cycle，找不到一個起點，所以可以直接return false
5. 如果有沒有先修課的課，我們就把其中一堂課從QUEUE裡取出來修完它
6. 修完它我們就不管它了，直接把它需要的課設為-1個
7. 針對其他堂課，我們檢查如果先修課包含剛剛那門修掉的課，那它們的先修課數目就-1，如果變成0了，就可以加到前面那個queue裡
8. 持續4~7的步驟，直到違反4而回傳false或順利遍歷完回傳true
   寫出來的解法如下，可以accepted：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // topological sort, to find the starting point
        // compute the number of course that have to study before that course
        vector<int> degrees(numCourses,0);
        for(int i=0;i<prerequisites.size();++i){
            ++degrees[prerequisites[i][1]];
        }
        
        // for every course, record the course that would study after that
        map<int, vector<int>> preCourseRev;
        for(int i=0;i<prerequisites.size();++i){
            preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
        }
        
        
        // a queue to record 0 degress point
         queue<int> q;
        for (int i=0; i<numCourses; ++i){
            if (degrees[i] == 0)
                q.push(i);
        }
        int cur=0;
        // detect if cycle
        for (int i=0; i<numCourses; ++i)
        {
            // from 0 degree point
            if (q.empty()){
                // no starting point. There are cycles.
                return false;
            }
            // starting from the first 0 degree point(class without prerequisities)
            cur = q.front();
            q.pop();
            // set to -1 indicates the point has been checked
            degrees[cur] = -1;
 
            // update the course requires cur
            for (int j: preCourseRev[cur])
            {
                --degrees[j];
                if (degrees[j]==0){
                    q.push(j);
                } 
            }
        }
        return true;
    }      
};

這是按照我對此演算法理解寫出來的版本，後來優化前面兩件事可以一起做+可以提早結束如下：
優化的是把前面1.2的計算寫在同一個for裡完成，並在最後加一個判斷如果queue的數量=剩下課程的數量，代表大家都沒先修課了，可以隨便按照順序也沒關係，因此可以直接回傳true。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // topological sort, to find the starting point
        // compute the number of course that have to study before that course
        vector<int> degrees(numCourses,0);
        
        // for every course, record the course that would study after that
        map<int, vector<int>> preCourseRev;
        for(int i=0;i<prerequisites.size();++i){
            preCourseRev[prerequisites[i][0]].push_back(prerequisites[i][1]);
            ++degrees[prerequisites[i][1]];
        }
        
        
        // a queue to record 0 degress point
         queue<int> q;
        for (int i=0; i<numCourses; ++i){
            if (degrees[i] == 0)
                q.push(i);
        }
        int cur=0;
        // detect if cycle
        for (int i=0; i<numCourses; ++i)
        {
            // from 0 degree point
            if (q.empty()){
                // no starting point. There are cycles.
                return false;
            }
            // starting from the first 0 degree point(class without prerequisities)
            cur = q.front();
            q.pop();
            // set to -1 indicates the point has been checked
            degrees[cur] = -1;
 
            // update the course requires cur
            for (int j: preCourseRev[cur])
            {
                --degrees[j];
                if (degrees[j]==0){
                    q.push(j);
                } 
            }
            // if there are no links now could be stop early
            if(q.size()==numCourses-i){
                return true;
            }
        }
        return true;
    }      
};

結語

說好的sum系列一直沒有繼續XD
倒數第4天了，繼續來完成它們吧！