LeetCode 207. 课程表
原题链接
中等
作者:
ShineShaye
,
2022-12-13 12:33:44
,
所有人可见
,
阅读 145
class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites) {
// 创建邻接表,记录所有点之间的依赖关系
vector<vector<int>> g(n);
vector<int> d(n);
for(auto& e : prerequisites){
// 课程对 [0, 1] 表示:想要学习课程 0 ,你需要先完成课程 1
// 说明第一个点依赖于第二个点,即拓扑图中有第二点指向第一个点的边
int a = e[1], b = e[0];
g[a].push_back(b);
// 记录每个点的入度
++d[b];
}
// 创建队列
queue<int> q;
// 把所有入度为0的点存入到队列中
for(int i = 0; i < n; ++i)
if(d[i] == 0)
q.push(i);
// 看当前有多少点入度为0,只有所有点都更新为入度为0说明存在拓扑排序
int cnt = 0;
while(q.size()){
auto tmp = q.front();
q.pop();
++cnt;
for(auto& x : g[tmp]){
--d[x];
if(!d[x]) q.push(x);
}
}
return cnt == n;
}
};