LeetCode 207. 课程表

思路：这是一道拓扑排序问题，拓扑排序听起来可能有点复杂，但实际上它是个相当直观的概念。想象一下，你有很多事情要做，但有些事情必须在另一些事情完成之后才能开始，就像你得先穿上袜子再穿鞋子

拓扑排序就是把这种图中的所有任务排成一个列表，让每个任务满足它的所有前置任务都在它前面。这样，当你按照列表的顺序去做事，就能保证每件事都在它需要的时候完成了。

实现拓扑排序

准备阶段：建立入度表

想象你有一张菜单，上面列出了所有要做的菜品以及它们的准备步骤。首先，你要确定哪些菜品可以立即开始准备（没有前置任务），哪些需要等待其他食材准备好。

• 入度表就像是一个记录板，它告诉我们每个菜品还需要多少项准备工作才能开始。如果一个菜品没有任何前置步骤，它的入度就是0。

实施阶段：广度优先遍历

1. 初始化：你创建了一个队列，用来存放那些可以立即开始准备的菜品（入度为0的节点）。

2. 处理菜品：你从队列中取出一个菜品开始准备（相当于从队列中出队一个节点）。假设这是“洗米做饭”这一步骤，完成之后，所有依赖于米饭的后续菜品（比如炒饭、盖浇饭）的准备条件就减少了一项（它们的入度各减1）。

3. 更新入度表：如果因为某个菜品的完成，使得其他菜品的准备条件全部满足了（它们的入度变为0），那么这些菜品就可以加入队列，等待下一轮处理。

4. 重复步骤：继续从队列中取出菜品准备，直到队列为空。每完成一个菜品（出队），表示一个任务完成，你就在总任务数上减去1。

代码：

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//检测这个vector数组中是否有环，vector<int>v;vector<int>indegree(numCourses, 0);//统计入度vector<vector<int>>graph(numCourses, v);//统计这个点是哪些节点的前置，也就是说他为哪些节点增加了入度for (int i = 0; i < prerequisites.size(); i++){indegree[prerequisites[i][0]]++;//统计入度graph[prerequisites[i][1]].push_back(prerequisites[i][0]);//prerequisites[i][1]是那些节点的前置条件}queue<int>q;for (int i = 0; i < numCourses; i++){if (indegree[i] == 0){q.push(i);//将入度为零的节点压入}}int res = 0;while (!q.empty()){int t = q.front();q.pop();res++;for (int i = 0; i < graph[t].size(); i++){indegree[graph[t][i]]--;if (indegree[graph[t][i]] == 0){q.push(graph[t][i]);}}}return res == numCourses;}
};