Problem: 210. 课程表 II

思路

本题是经典拓扑排序模板，通过DFS和BFS两种方式进行实现。

解题方法

1. DFS

   1. DFS方法的重点在于如何标记节点状态，初做题者如果只用未访问和已访问两种状态很容易陷入死结。
   2. 正确的做法是使用三种状态未访问，正在访问和已访问，原因是原因是如果想遇到环一定是遇到了本次DFS路径上的节点，他们属于特殊状态需要标记出。而遇到尚未访问的和别的路径访问过的节点都是没有问题的。

2. BFS

   1. BFS方法的重点在于多源，这也是BFS本身的一个特性，可以在图的多点同时进行BFS，参考题目994. 腐烂的橘子就很好地利用了这一特点。所以需要同时在图的多个地方进行操作时可以考虑多源BFS。
   2. 首先将节点入度统计出来，初始化时加入入度为0的节点，之后每次出队节点就把节点指向的节点的入度减少，再入队新产生的入度为0的节点，如此重复。
   3. 这一做法和手写拓扑排序十分类似。结果中如果没有包含所有节点即说明图中有环，无法拓扑排序。

Code

代码中同时有DFS和BFS两种实现

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> e(numCourses);
        vector<int> degree(numCourses);
        for(auto& prerequisity : prerequisites) {
            e[prerequisity[1]].push_back(prerequisity[0]);
            degree[prerequisity[0]]++;
        }

        auto res = dfs(numCourses, e);
        // auto res = bfs(numCourses, e, degree);
        return res;
    }

	/* DFS */

    vector<int> dfs(int n, vector<vector<int>>& e) {
        vector<int> vis(n, 0);  // 0未访问, 1正在访问, 2已被收录
        stack<int> s;

        bool valid = true;
        for(int i = 0; i < n; i++) {
            if(vis[i] == 0) dfs_rec(n, e, vis, s, valid, i);
        }
        if(valid == false) return {};

        vector<int> res;
        while(!s.empty()) {
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }

    void dfs_rec(int n, vector<vector<int>>& e, vector<int>& vis, stack<int>& s, bool& valid, int cur) {
        if(vis[cur] == 1) {
            valid = false;
            return;
        }
        if(vis[cur] == 2) {
            return;
        }

        vis[cur] = 1;
        for(auto eg : e[cur]) {
            dfs_rec(n, e, vis, s, valid, eg);
        }
        s.push(cur);

        vis[cur] = 2;
        return;
    }

	/* BFS */

    vector<int> bfs(int n, vector<vector<int>>& e, vector<int>& degree) {
        queue<int> q;
        for(int i = 0; i < n; i++) {
            if(degree[i] == 0) q.push(i);
        }

        vector<int> res;
        while(!q.empty()) {
            auto cur = q.front();
            q.pop();
            res.push_back(cur);
            for(auto& eg : e[cur]) {
                degree[eg]--;
                if(degree[eg] == 0) q.push(eg);
            }
        }

        if(res.size() < n) return {};
        return res;
    }
};