青海网站开发公司,做直播网站软件有哪些软件下载,wordpress 主题 zuopin,如果做网站Problem: 210. 课程表 II 文章目录 思路解题方法Code 思路
本题是经典拓扑排序模板#xff0c;通过DFS和BFS两种方式进行实现。
解题方法 DFS DFS方法的重点在于如何标记节点状态#xff0c;初做题者如果只用未访问和已访问两种状态很容易陷入死结。正确的做法是使用三种状… Problem: 210. 课程表 II 文章目录 思路解题方法Code 思路
本题是经典拓扑排序模板通过DFS和BFS两种方式进行实现。
解题方法 DFS DFS方法的重点在于如何标记节点状态初做题者如果只用未访问和已访问两种状态很容易陷入死结。正确的做法是使用三种状态未访问正在访问和已访问原因是原因是如果想遇到环一定是遇到了本次DFS路径上的节点他们属于特殊状态需要标记出。而遇到尚未访问的和别的路径访问过的节点都是没有问题的。 BFS BFS方法的重点在于多源这也是BFS本身的一个特性可以在图的多点同时进行BFS参考题目994. 腐烂的橘子就很好地利用了这一特点。所以需要同时在图的多个地方进行操作时可以考虑多源BFS。首先将节点入度统计出来初始化时加入入度为0的节点之后每次出队节点就把节点指向的节点的入度减少再入队新产生的入度为0的节点如此重复。这一做法和手写拓扑排序十分类似。结果中如果没有包含所有节点即说明图中有环无法拓扑排序。
Code
代码中同时有DFS和BFS两种实现
class Solution {
public:vectorint findOrder(int numCourses, vectorvectorint prerequisites) {vectorvectorint e(numCourses);vectorint 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 */vectorint dfs(int n, vectorvectorint e) {vectorint vis(n, 0); // 0未访问, 1正在访问, 2已被收录stackint 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 {};vectorint res;while(!s.empty()) {res.push_back(s.top());s.pop();}return res;}void dfs_rec(int n, vectorvectorint e, vectorint vis, stackint 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 */vectorint bfs(int n, vectorvectorint e, vectorint degree) {queueint q;for(int i 0; i n; i) {if(degree[i] 0) q.push(i);}vectorint 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;}
};
