這題是graph的問題。

Input

這題是大學修課擋修的問題，我是沒有遇過擋修啦，所以沒什麼感覺，但程式一跑，就會直接宣布你能不能畢業還挺微妙的。

　
　
看了一下Example，看起來也是在圖裡判斷有無環的產生就行，不過這次是有向圖，有環表示無解，無環表示修得完。


　
　
恩～這樣用矩陣可能會太大？

　
　
　

思路：

總之先用adj list，把課與課之間的關係用有向圖的形式存起來，然後用DFS的概念好了，去遍歷圖上的點，主要就是如果點有被discover兩次，就代表圖上有環。
　
　
　

筆記：

對c++的vector真的很不熟，每次用完每次忘，記一下筆記好了0.0

vector可用於宣告動態陣列，我記得特別是因為宣告時佔用的是連續記憶體，所以存取很快，用得時候宣告vector，然後用角括號<>包住此vector的型態。

宣告int的2維vector array的話，就用vector<>包住vector<int>就行。

跟直接宣告的2維陣列不同，vector array不能用一般c/c++的for調用。
需要用iterator或for( auto el: vectorname )
　
　
　

程式碼：

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adjlist(numCourses);
        for (auto pair: prerequisites){
            adjlist[pair[1]].push_back(pair[0]);
        }
        
        vector<bool> discover(numCourses, false), finish(numCourses, false);
        for (int i = 0; i < numCourses; i++) {
            if (!finish[i]) {
                if(cyclic(adjlist, discover, finish, i)){
                    return false;
                }
            }
                
        }
        
        return true;
    }
private:
    bool cyclic(vector<vector<int>>& adjlist, vector<bool>& discover, vector<bool>& finish, int curr_node) {
        if (discover[curr_node]) //有沒有被探索過啊？
            return true;
        if (finish[curr_node]) //這點的neighbor都已經被探索完了？
            return false;
        discover[curr_node] = true;
        for (auto v : adjlist[curr_node]) //來搜尋neighbor
            if (cyclic(adjlist, discover, finish, v))
                return true;
        discover[curr_node] = false; finish[curr_node] = true;//把這點的狀態切換成已探索完成
        return false;
    }
};

Bug參考

是說，有段時間我一直遇到Time limit的問題，後來發現是我使用副程式時，沒有用&把變數位置傳過去，難怪我的recursive永遠跑不完:3
　
　
參考：
https://youtu.be/PMMc4VsIacU
https://leetcode.com/problems/course-schedule/discuss/58509/C%2B%2B-BFSDFS
https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html