网站交换链接的常见形式,大佛寺广州网站,郑州做手机网站,长沙建站模板原题链接#x1f517;#xff1a;课程表 难度#xff1a;中等⭐️⭐️
题目
你这个学期必须选修 numCourses 门课程#xff0c;记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出#xff0c;其中 prerequisites[i]…原题链接课程表 难度中等⭐️⭐️
题目
你这个学期必须选修 numCourses 门课程记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出其中 prerequisites[i] [ai, bi] 表示如果要学习课程 ai 则 必须 先学习课程 bi。
例如先修课程对 [0, 1] 表示想要学习课程0你需要先完成课程 1 。 请你判断是否可能完成所有课程的学习如果可以返回true否则返回false 。
示例 1
输入numCourses 2, prerequisites [[1,0]] 输出true 解释总共有 2 门课程。学习课程 1 之前你需要完成课程 0 。这是可能的。
示例 2
输入numCourses 2, prerequisites [[1,0],[0,1]] 输出false 解释总共有 2 门课程。学习课程 1 之前你需要先完成课程 0 并且学习课程 0 之前你还应先完成课程 1 。这是不可能的。
提示
1 numCourses 20000 prerequisites.length 5000prerequisites[i].length 20 ai, bi numCourses prerequisites[i] 中的所有课程对 互不相同
拓扑排序 拓扑排序是图论中的一个概念它对有向无环图DAGDirected Acyclic Graph中的顶点进行线性排序使得对于任何一条有向边 U - V顶点 U 都在顶点 V 的前面。这种排序不是唯一的。拓扑排序常用于任务调度、课程规划等场景。 以下是拓扑排序的一般步骤 计算所有顶点的入度入度是指有多少条边指向该顶点。对于图中的每个顶点初始化一个计数器来记录入度。 将所有入度为0的顶点加入队列入度为0的顶点表示没有依赖可以首先进行排序。 处理队列中的顶点 从队列中移除一个顶点并将其加入到拓扑排序的结果列表中。遍历该顶点的所有邻接点将每个邻接点的入度减1因为它们的一个依赖已经完成。如果某个邻接点的入度变为0,将其加入队列。 重复步骤3直到队列为空。 检查环如果拓扑排序的结果列表中的顶点数量等于原始图中的顶点数量则图中没有环否则存在环无法完成拓扑排序。 拓扑排序的算法可以用多种方式实现包括Kahn算法和DFS深度优先搜索。 拓扑排序的时间复杂度通常是 O(VE)其中 V 是顶点数E 是边数。空间复杂度为 O(V)用于存储访问状态和排序结果。 题解
解题思路 LeetCode 上的 “课程表” 问题问题编号207是一个典型的图论问题主要考察了图的深度优先搜索DFS和拓扑排序的应用。 以下是这个问题的解题思路 理解问题首先明确题目要求我们判断是否能够完成所有课程的学习。这等价于判断图中是否存在环因为如果存在环则表示有课程无法满足其所有先修条件。 构建图根据给定的先修关系列表 prerequisites 构建一个有向图。可以使用邻接表来表示这个图其中每个节点代表一门课程边表示先修关系。 检测环使用深度优先搜索DFS来检测图中是否存在环。在DFS过程中使用两个集合来记录访问状态 visited记录已经访问过的节点。recStack递归栈记录当前递归路径上的节点用于检测环。 DFS逻辑 对于每个未访问的节点执行DFS。如果当前节点已经在 recStack 中表示找到了一个环返回 false。如果当前节点已经访问过并且不在 recStack 中可以跳过。将当前节点加入 visited 和 recStack。对当前节点的所有邻接节点递归执行DFS。递归返回后将当前节点从 recStack 中移除。 拓扑排序如果所有节点都可以通过DFS访问且没有检测到环那么图是可拓扑排序的即可以完成所有课程的学习。 c demo
#include iostream
#include vector
#include queueusing namespace std;class Solution {
public:bool canFinish(int numCourses, vectorpairint, int prerequisites) {vectorint indegrees(numCourses, 0);vectorvectorint graph(numCourses);// 构建图并计算入度for (auto pre : prerequisites) {graph[pre.first].push_back(pre.second);indegrees[pre.second];}// 拓扑排序vectorint topsort;queueint q;for (int i 0; i numCourses; i) {if (indegrees[i] 0) {q.push(i);}}while (!q.empty()) {int course q.front();q.pop();topsort.push_back(course);for (int pre : graph[course]) {indegrees[pre]--;if (indegrees[pre] 0) {q.push(pre);}}}// 如果所有课程都被排序了图中没有环return topsort.size() numCourses;}
};int main() {Solution solution;// 测试用例vectorpairint, int prerequisites { {1, 0}, {0, 1} };int numCourses 4;bool result solution.canFinish(numCourses, prerequisites);if (result) {cout It is possible to finish all courses. endl;}else {cout It is not possible to finish all courses. endl;}return 0;
}输出结果 It is not possible to finish all courses. 代码仓库地址canFinish
