Leetcode 207. Course Schedule | 含C++笔记

这题是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;
    }
};