LeetCode HOT100 - 课程表

拓扑排序

课程之间存在依赖关系，只有所有前置课程修完了才能学习下一个课程

建立依赖边，用入度来表示还有多少课程没学习

入度为 0 的课程可以开始学习

要注意队列的函数，加入元素使用 push，队列的元素使用 front，删除用 pop

class Solution {
public:bool canFinish(int n, vector<vector<int>>& pre) {vector<int> cnt(n);vector<vector<int>> suf(n);for (auto a : pre) {cnt[a[0]]++;suf[a[1]].emplace_back(a[0]);}queue<int> q;int num = n;for (int i = 0; i < n; i++) {if (!cnt[i]) {q.push(i);num--;}}while (!q.empty()) {int x = q.front();q.pop();for (int y : suf[x]) {cnt[y]--;if (!cnt[y]) {num--;q.push(y);}}}return num == 0;}
};

dfs 下次一定