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