拓扑排序CSP-S

💡 核心思想

拓扑排序将 DAG（有向无环图）中的所有顶点排成一个线性序列，使得每条边的起点都在终点之前。常用 Kahn 算法（BFS，不断删除入度为0的节点）实现。也可用于检测图中是否有环。

🎯 直觉理解

拓扑排序就是把有向无环图（DAG）的节点排成一行，保证每条边的起点都在终点前面。就像排课：先修课必须在后修课之前。有环的图排不出来——拓扑排序也能用来判环。

算法（Kahn）：统计每个点入度，入度为 0 的点先入队；每取出一个点，把它所有后继的入度减 1，减到 0 就入队。取出的顺序就是拓扑序。

拓扑序不唯一，但"能否排出来"是确定的。配合 DP 很好用：按拓扑序计算最长路、方案数等，因为处理到某个点时它的所有前驱都已经算完。

📝 算法流程

1. 计算所有节点的入度
2. 将入度为0的节点入队
3. 出队一个节点，将其所有邻居入度减1
4. 若邻居入度变为0则入队，重复直到队空

$$\text{如果拓扑序列长度} < n \text{，则图有环}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector> adj(n+1);
    vector indeg(n+1, 0);
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }
    queue q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    vector order;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }
    if (order.size() < n) cout << "有环" << endl;
    else { for (int x : order) cout << x << " "; cout << endl; }
    return 0;
}

⚠️ 常见坑点

📚 相关题目