207.course-schedule.md

207. 课程表

一，题面

1. 描述
   • 有 numCourse 门课程，记为 0 到 numCourse-1 。
   • 先修课程列表：例如，[0,1]表示，想要学习课程 0 ，你需要先完成课程 1。
   • 给定numCourse和先修课程列表prerequisites，
   • 判断是否可完成所有课程的学习？
2. 示例
   • 输入: 2, [[1,0],[0,1]]
   • 输出: false
   • 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

二，思路

1. 本题目可简化为，判断一个有向图里，是否存在环，或者是否存在一个拓扑排序序列
2. 思路：BFS。

   • (1)步骤

   • 将所有入度为0的节点入队。

   • 队列首元素cur出队，拓扑排序序列里元素个数 count 加一。

   • 对于cur的每个邻接节点v：

     • v的入度减一，
     • 此时，入度为0的v入队。

   • BFS结束，如果 count等于numCourse，

   • 则存在一个拓扑排序序列，即不存在环（可完成所有课程的学习）。

   • (2)基于此，我们需要做以下定义：

     • 将先修课程列表转化为有向图的常见表示（比如邻接矩阵）。
       • 本题是转化为【节点，邻接节点列表】形式。
     • 定义入度数组，
     • 假设存在一种拓扑排序序列，元素个数是 count 。

三，实现

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> MatrixGraph(numCourses, vector<int>{});
        vector<int>indegreee(numCourses,0);
        for(auto pair: prerequisites){
            MatrixGraph[pair[1]].push_back(pair[0]);            
            indegreee[pair[0]]++;
        }
        int i;
        queue<int>Q;
        for(i=0; i<numCourses; i++){
            if(indegreee[i]==0)
                Q.push(i);
        }
        int cur, Topology_Seq_Count=0;
        while(!Q.empty()){
            cur = Q.front();
            Q.pop();

            Topology_Seq_Count ++;
            for(auto v: MatrixGraph[cur]){
                
                indegreee[v] --;
                if(indegreee[v]==0)
                    Q.push(v);
            }
        }
        return Topology_Seq_Count==numCourses;
    }
};