[210. 课程表 II] 拓扑排序模板(DFS+BFS)

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;}
};