题目

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/course-schedule
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

 

思路

### 解题思路

题目大意->刚开始也是看不懂题目，但是慢慢捋也捋清楚了，建议先看一次官方调解，看视频最好

给你一个numCourses门课，然后给你一个课程关系表，在这个关系表里，你可以直接学的是不需要关系的科目，这里我们叫入度，在课程关系表中的，第二列表示，想要学习这个科目，你必须先学习第一列的科目，也就是必须用有关系才可以学，我们这里叫出度，那是不是有既没有入度也没有出度的课程呢？是有的，那就是那些没有先在课程关系表中的科目，比如5 [[1,4],[2,4],[3,1],[3,2]] 其中0就是这种，

# 广度优先

读懂题目，其实还是挺简单的，我们定义一个科目数组，保存每个科目的入度，入度为0的就说明可以直接学习的科目，入度为大于0的就说明需要先学别的，所以如果当数组全部为0说明我们可以直接全部学完所有科目，如果数组全部大于0说明我们不管怎么样学习，不管先学那个，我们都没办法学完

所以我们先将课程关系表转换为科目数组，然后我们优先学入度为0的科目，然后将科目为0的所对应的出度的科目的入度减1，可能有点绕，其实就是我学完了一个科目，那么我是不是就可以把那些以我为入度的科目，入度减少1，说明我这个科目学完了

然后每次都找为0的科目数值，当科目数组全部为0时，就说明我们可以学完

代码

/*
*bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize)
bool canFinish：判断我是否能学完numCourses 门课程
int numCourses：学习课程的数量
int** prerequisites：课程关系表
int prerequisitesSize：课程关系表长度
int* prerequisitesColSize:课程关系表的列长
返回值：能学完返回true
        不能返回false
*/
bool canFinish(int numCourses, int** prerequisites, int prerequisitesSize, int* prerequisitesColSize){
    if(prerequisitesSize == 0)
    {
        return true;
    }
    int * ans = malloc(sizeof(int) * numCourses);
    int i = 0;
    for(i = 0; i < numCourses; i++)//初始化为0
    {
        ans[i] = 0;
    }
    int m = prerequisitesSize;
    int j = 0;
    int res = 0;
    for(i = 0; i < prerequisitesSize; i++)//更新每个点的入度
    {
        ans[prerequisites[i][1]]++;
    }
    for(i = 0; i < numCourses; i++)
    {
        if(ans[i] == 0)//当前科目i学完了
        {
            res++;//学完的科目总数+1
            if(res == numCourses)//总数等于我要学的科目，说明我全部可以学完
            {
                return true;
            }
            for(j = 0; j < prerequisitesSize; j++)//更新以我为入度的点的入度
            {
                if(prerequisites[j][0] == i)
                {
                    ans[prerequisites[j][1]]--;
                }
            }
            ans[i]--;//避免重复比较
            i = -1;
        }
    }
    return false;
}

时间空间复杂度