LeetCode刷题实战207：课程表-技术圈

LeetCode刷题实战207：课程表

共 3512字，需浏览 8分钟

· 2021-03-14

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 课程表，我们先来看题面：

https://leetcode-cn.com/problems/course-schedule/

For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.

题意

反你这个学期必须选修 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 。这是不可能的。

解题

https://www.jianshu.com/p/8d7b8b324079

思路分析：经典的拓扑排序问题。

先将入度为 0的顶点加入一个处理队列

每次取出入度为 0的顶点, 将这个顶点的所有邻接点入度 - 1, 再将入度为 0的点加入队列

比较课程数与处理的顶点数是否相等

时间复杂度O(n + m), 空间复杂度O(n + m), 其中 n为课程数, m为先修课程数

class Solution 
{
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
    {
        if (prerequisites.empty()) return true;
        map<int, vector<int>> adjcent;
        vector<int> indegree(numCourses, 0);
        queue<int> q;
        int count = 0;
        for (auto& course : prerequisites)
        {
            adjcent[course[1]].push_back(course[0]);
            ++indegree[course[0]];
        }
        for (int i = 0; i < numCourses; i++) if (!indegree[i]) q.push(i);
        while (q.size())
        {
            auto cur = q.front();
            q.pop();
            ++count;
            for (auto first : adjcent[cur])
            {
                --indegree[first];
                if (!indegree[first]) q.push(first);
            }
        }
        return count == numCourses;
    }
};