leetcode207. 课程表-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode207. 课程表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

你这个学期必须选修 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、创建一个领接表存放所有课程之间的学习关系，所以我们开一个二维数组g存放每门课和它的后继课程；创建一个大小为numCourses的一维数组inDrgree 存放所有课程的先修课程（入度）。最开始先遍历prerequisities数组，由于prerequisities数组中给的关系是先给后继课程，再给前驱课程，所以存放到g数组的时候要注意一下顺序，前驱课程在前，后继课程在后。
2、遍历存放所有点之间的依赖关系的数组（这题是prerequisities数组），统计所有入度为0的节点，即没有任何先修课程的课程。
3、有一个队列存放所有的点（入队顺序表示学习课程的顺序），将所有入度为0的节点入队。然后进行BFS，不断取出队列中的队头元素，并且更新这个点的所有后继节点（这里队头元素是所有入度为0的节点，表示已经学习过的课程，则这门课的所有后继课程的先修课程数量减一，也就是学了一门先修课程），然后判断减一之后，后继课程们是否已经没有了先修课程（入度是否为0），如果入度为0，就把这门课加入到队列中。当然，每取出一门课程，我们都有一个计数变量cnt加一，表示已经修过多少门课程。
4、重复第（2）步，直到队列为空，这时判断一下修过的课程数量cnt是否和课程总数numCourses，如果是，说明存在一种拓扑序列，可以学习完所有课程。如果不相等，说明不存在。文章来源地址https://www.toymoban.com/news/detail-423116.html

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    vector<int> indegree(numCourses, 0);//每个课程的入度
    for (auto courseEdge : prerequisites) //边数组转成邻接表
    {
        adj[courseEdge[1]].push_back(courseEdge[0]);//a b代表b->a的边
        indegree[courseEdge[0]]++;//a的入度+1
    }
    queue<int> q;//辅助队列
    int res = 0;
    for (int course = 0; course < numCourses; course++)
        if (indegree[course] == 0)
            q.push(course);//入度为0的课程入队列
    while (!q.empty())//继续拓扑排序
    {
        int cur = q.front();//当前课程
        q.pop();
        res++;
        vector<int>  courseArr = adj[cur];//后修课程
        for (auto postCourse : courseArr)//遍历每个后修课程
        {
            indegree[postCourse]--;//删除该边 即后修课程的入度-1 因为当前节点唯一访问 所以不需要删除邻接表
            if (indegree[postCourse] == 0)//删除边后 该节点的入度为0且未在拓扑排序中
                q.push(postCourse);//入队列
        }
    }
    return res == numCourses ? true : false;
}

int main() {
	vector<vector<int> > cours{ {1,0} };
	int n = 2;
	bool res = canFinish(n, cours);
	cout << boolalpha << res << endl;	
	return 0;
}