做购物网站需要学哪些,私人网站建设步骤,app研发流程,室内设计网站建设题面#xff1a; Link#xff1a;LeetCode 207 课程表
思路#xff1a;
首先很容易想到如果图中存在有向环#xff0c;则表示这个环里的课是没法学习的#xff08;因为环里的课都在等待自己的前置课被学习#xff09;。 例如#xff1a; 0 → 1 → 2 → 0 0\rightarro…题面 LinkLeetCode 207 课程表
思路
首先很容易想到如果图中存在有向环则表示这个环里的课是没法学习的因为环里的课都在等待自己的前置课被学习。 例如 0 → 1 → 2 → 0 0\rightarrow1\rightarrow2\rightarrow0 0→1→2→0
简单用拓扑排序的思想解释一下容易想到只有 入度为 0 的顶点课是可以一开始就直接学习的。如果有顶点 u u u 被遍历了 u u u 课程被学习了其指向的所有邻接点的入度就可以减一邻接点的前置课 u u u 已经学习了因此 u u u 对它们已经没有约束了。
因此只有 有向无环图DAG 才是合法的。 有个性质能拓扑排序的图一定是有向无环图DAG有向无环图一定能拓扑排序。
DAG的判断一般就两种方法
用入度搞个拓扑排序可以直接 DFS 判断是否存在 有向环对图进行一遍 DFS在得到的 DFS 树上看看有没有连向祖先的非树边返祖边。如果有的话那就有环了。简单来说直接判断 DFS 的搜索过程中是否有结点被二次遍历了有就是出现环了。
代码
拓扑排序
bool canFinish(int numCourses, vectorvectorint prerequisites) {vectorint d(numCourses, 0);vectorvectorint edges(numCourses);for(const auto edge : prerequisites) {edges[edge[1]].emplace_back(edge[0]); d[edge[0]];}int visited 0;queueint q;for(int i 0; i numCourses; i)if(!d[i])q.push(i);while(!q.empty()) {visited;int u q.front(); q.pop();for(const auto v : edges[u]) {--d[v];if(!d[v]) q.push(v);}}return visited numCourses;
}DFS判断环
class Solution {
private:vectorvectorint edges;vectorint visited;bool valid true;public:void dfs(int u) {visited[u]true;if(!valid) return ;for(const auto v : edges[u]) {if(visited[v] 1) {valid false;return ;}if(valid !visited[v]) dfs(v);}visited[u];return ;}bool canFinish(int numCourses, vectorvectorint prerequisites) {edges.resize(numCourses, vectorint());visited.resize(numCourses, false);for(const auto edge : prerequisites) edges[edge[1]].emplace_back(edge[0]);for(int i0;inumCourses valid;i)if(!visited[i])dfs(i);return valid;}
};
