Leetcode: 210. Course Schedule II | 含C++笔记

Course Schedule I的延伸，这次要排出课程顺序。

思路

有大概想到去找node的顺序跟课程顺序有关，结果发现DFS离开结束点的顺序颠倒过来，就是这题要的output～所以用个vector纪录就行了。
　
　
　

笔记

c++要回传空阵列时，用大括号。

return {}; //correct
return []; 

想把vector的el顺序颠倒，可以用reverse()，加一行程序，vectorname的顺序就颠倒了

for(auto el, vectorname)
    cout << el << " ";
reverse(vectorname.begin(), vectorname.end();
for(auto el, vectorname)
    cout << el << " ";

程序码

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adjlist(numCourses);
        for(auto el: prerequisites) {
            adjlist[el[1]].push_back(el[0]);
        }
        
        vector<bool> discover(numCourses, false), finish(numCourses, false);
        
        vector<int> q;
        for(int i = 0; i < numCourses; i++) 
            if(!finish[i])
                if(cyclic(adjlist, discover, finish, i, q))
                    return {};
        
        reverse(q.begin(), q.end());
        return q;
    }
private:
    bool cyclic(vector<vector<int>>& adjlist, vector<bool>& discover, vector<bool>& finish, int curr_node, vector<int>& q) {
        if (discover[curr_node])
            return true;
        if (finish[curr_node])
            return false;
        discover[curr_node] = true;
        for(auto el: adjlist[curr_node]) {
            if(cyclic(adjlist, discover, finish, el, q))
                return {};
        }
        discover[curr_node] = false; finish[curr_node] = true;
        q.push_back(curr_node);
        return false;
    }
};

Bug参考

重打一次昨天的cyclic()时，一直跑出error type-ed: cannot have a name的错误，後来发现是我adjlist的宣告型态少打一个角括号<
　
　
赚到一天耶
　
参考：
https://web.ntnu.edu.tw/~algo/DirectedAcyclicGraph.html
https://ithelp.ithome.com.tw/articles/10266857