Kahn 算法

一句话理解

Kahn：不断取入度 0 的点。

为什么要学

队列实现拓扑。

讲解

能取 n 个点则无环，否则有环。

例子

while (q.size()) {
    int u = q.front(); q.pop();
    for (int v : g[u]) if (--indeg[v] == 0) q.push(v);
}

类似 BFS。

常见错误

• 有环仍输出部分序当全部。
• 多个入度 0 时顺序题目有字典序要用优先队列。