Course Schedule I,II

detect cycle的题。

1、用dfs做：

• 需要一个数据结构来储存当前走过的路径，每次走完这整条路成功的话，就应该把当前的路径走过与否改成false来返回，如果这条路失败，直接返回false
• 需要一个数据结构来储存总共走的路径，因为node间不一定全部有连接，而我们无需再检查已经走过的node
• 需要一个数据结构来储存当前节点之后是什么路径

class Solution {
private:
    unordered_map<int, vector<int>> map;
    bool dfs(int numCourses, int cur, vector<int>& curPath, vector<int>& totalPath, vector<int>& res)
    {
        if (curPath[cur]) return false; // detect cycle
        if (totalPath[cur]) return true; // avoid duplicates
        curPath[cur] = totalPath[cur] = 1; // explore a new node
        for (int i: map[cur])
        {
            if (!dfs(numCourses, i, curPath, totalPath, res)) return false;
        }
        curPath[cur] = false; // undo current
        res.push_back(cur); // record the valid current path
        return true;
    }
    
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) 
    {
        vector<int> curPath(numCourses);
        vector<int> totalPath(numCourses);
        vector<int> res;
        for (auto &p: prerequisites) map[p.second].push_back(p.first); // make graph
        for (int i = 0; i < numCourses; ++i) // in this form we won't lose information about unconnected vertexes
        {
            if (!totalPath[i] && !dfs(numCourses, i, curPath, totalPath, res)) return {};
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

2、Kahn's algorithm

搞清楚Kahn's algorithm。这个算法的insight是，对于一个connected DAG来说，至少有一个node它的incoming edges是0。简单想一下，如果graph的头和尾是连起来的话，那么就没有incoming edges是0了。如果我们每一次都将incoming edges是0的node加入到一个array里面，比如1->2->3，第一次把1加入，这时候把它的outgoing edges都去掉，于是把2加入，再去掉edge，再把3加入，这样的话array数量是3==node数量，排列是123。对于1->2->3->2来说，当我们把1加入array并去掉edge的时候，会发现2还有incoming edge，所以不能加入array，这样一来整个图就没有incoming edge为0的node了，但我们并没有遍历整个图，所以说这个图是有圈圈的。

所以这个算法的步骤就是：将所有incoming edge为0的node加入到一个array中，每次加入时去除outgoing edges，这样不断循环，如果图中没有符合条件的node了，我们也已经遍历完了这个图，那么所得array就是拓扑排序的顺序。这个算法的base case是一个node的时候，incoming edge=0。其它更复杂的图通过处理都是想回到基于这个base case的判断上来。

至于说为什么所得array就是拓扑排序的顺序，因为每次我们都是将node的incoming edge是0是那个node加入到array，也就是把处于顺序优先的node先放进array了，那最后所得必然就是顺序了。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) 
    {
        unordered_map<int, vector<int>> map_next;
        queue<int> next;
        vector<int> edges(numCourses);
        vector<int> res;
        for (auto &ele: prerequisites)
        {
            map_next[ele.second].push_back(ele.first);
            edges[ele.first]++;
        }
        for (int i = 0; i < edges.size(); ++i)
        {
            if (!edges[i]) next.push(i); 
        }
        while (!next.empty())
        {
            int top = next.front();
            next.pop();
            res.push_back(top);
            for (auto num: map_next[top])
            {
                edges[num]--;
                if (!edges[num]) next.push(num);
            }
        }
        return res.size() == numCourses ? res : vector<int>();
    }
};

在这个算法中，用stack, vector, queue，都可以得到正确的结果。