题目描述:
你这个学期必须选修 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 <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i]
中的所有课程对 互不相同
题目链接:
. - 力扣(LeetCode)
解题主要思路:
经典的bfs拓扑排序题,先借助stl容器将有向图和节点对应的入度记录下来,接着先将入度为0的节点入队列,当队列不为空时循环进行以下操作:
1. 提取头节点,对头节点的相邻节点去边
2.判断邻居节点的入度是否为0,若为0则加入到队列中
最后再遍历记录节点对应的入度容器
若存在入度不为0的节点,则说明我们所构建的有向图中存在环的情况,这种情况就是题目所提供的例2,是不合法不存在的,所以返回false;
若不存在入度不为0的节点,则说明我们所构建的有向图是AOV图,这种情况就是题目所提供的例1,是合法存在的,所以返回true。
解题代码:
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {unordered_map<int, vector<int>> edges; // 邻接表vector<int> in(numCourses); // 记录入度// 建图for (auto& e : prerequisites) {int a = e[0], b = e[1]; // b -> aedges[b].push_back(a);++in[a];}// 拓扑排序 -- bfs// 先找到入度为0的节点,加入que中queue<int> que;for (int i = 0; i < numCourses; ++i) {if (in[i] == 0) que.push(i);}// bfswhile (!que.empty()) {int t = que.front(); que.pop();// 修改相连的边for (auto& e : edges[t]) {--in[e];if (in[e] == 0) que.push(e);}}// 检测是否还有节点的入度不为0(判断是否有环) for (auto& e : in) {if (e) return false;}return true;}
};