小旭讲解 LeetCode 207. 课程表
小旭讲解 LeetCode 207. 课程表

原题

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

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

示例 1:

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。


示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

 

提示:

  • 输入的先决条件是由 边缘列表 表示的图形,而不是 邻接矩阵 。详情请参见图的表示法。
  • 你可以假定输入的先决条件中没有重复的边。
  • 1 <= numCourses <= 10^5

思路一 – 拓扑排序

这是一道图的问题,题目给定了若干条有向边,我们可以使用这些有向边构建出一个图。构建的方法有两种:邻接表,邻接矩阵。

这里面我们使用比较简单的方式 —— 邻接矩阵 表示一个有向图。形如下面:

   0列 1列
0行 1  1
1行 0  1

上面 (0, 1) 的值为 1,代表存在一个从 0 出发,指向 1 的一条边。

上面 (1, 0) 的值为0,代表不存在一个从 1 出发,指向 0 的一条边。

题目实际上是要求判断这个有向图中是否存在环。如果存在环那么返回 false,否则返回 true。

判断有向图中是否有环可以使用拓扑排序,关于拓扑排序,我曾经录了一个视频来讲解,有兴趣的同学可以看下:拓扑排序 —— 小旭讲解 LeetCode 269. Alien Dictionary – EP14

代码

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& ps) {
        vector<vector<int>> m(n + 5, vector<int>(n + 5, 0));
        vector<int> id(n + 5, 0);
        for (auto &p : ps) {
            m[p[1]][p[0]] = 1;
            id[p[0]]++;
        }
        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (id[i] == 0) q.push(i);
        }
        int cnt = 0;
        while (!q.empty()) {
            auto no = q.front();
            q.pop();
            ++cnt;
            for (int nno = 0;nno < n; ++nno) {
                if (m[no][nno] == 0) continue;
                if (--id[nno] == 0) q.push(nno);
            }
        }
        return cnt == n;
    }
};

复杂度分析

时间复杂度:O(V + E) V 代表图的节点数,E 代表图的边数
空间复杂度:O(V^2)

思路二 – 深度优先搜索

在 DFS 时,我们将节点进行标记,一共有三种状态:

  • 未访问 0
  • 访问中 1
  • 已访问 2

如果在搜索时,搜到了一个在访问中的节点,那么此时出现了环。即返回 false。

代码

class Solution {
public:
    vector<vector<int>> ps, m;
    // vis 0 未访问 1 访问中 2 已访问
    vector<int> vis;
    int n;
    bool dfs(int no) {
        if (vis[no] == 1) return false; // 有环
        if (vis[no] == 2) return true; // 曾经搜索过
        vis[no] = 1;
        for (int nno = 0; nno < n; ++nno) {
            if (m[no][nno] == 0) continue;
            if (!dfs(nno)) return false;
        }
        vis[no] = 2;
        return true;
    }
    bool canFinish(int _n, vector<vector<int>>& _ps) {
        n = _n, ps = _ps;
        m = vector<vector<int>>(n, vector<int>(n, 0));
        vis = vector<int>(n, 0);
        for (auto &p : ps) {
            m[p[1]][p[0]] = 1;
        }
        for (int no = 0; no < n; ++no) {
            if (!dfs(no)) return false;
        }
        return true;
    }
};

复杂度分析

时间复杂度:O(V + E)
空间复杂度:O(V^2)

参考

[1]. LeetCode 原题. https://leetcode-cn.com/problems/course-schedule/
[2]. 拓扑排序 —— 小旭讲解 LeetCode 269. Alien Dictionary – EP14. https://www.bilibili.com/video/BV1CJ411S7Wj

本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/xiaoxu-tutorial-leetcode-207-course-schedule/
最后修改日期:2020年8月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。