207. 课程表

难度：🟡 Medium | 标签：图论、拓扑排序、BFS | 状态：⬜ LeetCode 链接

思路

拓扑排序判环：

1. 构建邻接表 + 入度数组
2. 所有入度 0 的入队
3. BFS：弹出一个，相邻入度 -1，归零的入队，计数
4. 计数 == n 则无环

代码

class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& prereq) {
        vector<vector<int>> g(n);
        vector<int> ind(n, 0);
        for (auto& e : prereq) { g[e[1]].push_back(e[0]); ind[e[0]]++; }
        queue<int> q;
        for (int i = 0; i < n; ++i) if (ind[i] == 0) q.push(i);
        int done = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            ++done;
            for (int v : g[u]) if (--ind[v] == 0) q.push(v);
        }
        return done == n;
    }
};

复杂度

• 时间 O(V + E)，空间 O(V + E)

易错 / 回顾

• 邻接表方向：先修课 → 后修课
• DFS 三色法（白 / 灰 / 黑）也能判环，但 BFS 拓扑更直观
• 输出拓扑序：210 题