原题
你这个学期必须选修 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/
留言