拓扑排序CSP-S

💡 核心思想

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

🎯 直觉理解

想象你要安排课程表：有些课有先修要求（数据结构需要先学编程）。拓扑排序就是找到一种上课顺序，确保每门课的先修课都排在它前面。如果课程之间有循环依赖（A要B先修，B要A先修），就不可能排出顺序——说明有环。

📝 算法流程

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

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

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n+1);
    vector<int> 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<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    vector<int> 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;
}

⚠️ 常见坑点

📚 相关题目