本讨论 专门 讲解 何为 拓扑排序

本题题解： https://hydro.ac/p/luogu-P2712/solution/68641f28345cc6899b2b6f31

什么是拓扑排序？

是一类典型的图上无权问题 拓扑排序是对有向无环图（DAG, Directed Acyclic Graph）的所有顶点的一种线性排序，使得对于图中的每一条有向边 (u, v)，u 在排序中总是位于 v 的前面。如果图中存在环，则无法进行拓扑排序。

例子

无环

比如你期末数学考的非常好，考了0分，你妈高兴的就要拿扫把抽你（别介意，仅为讲解~）

事件A（你考了0分） 事件B（你妈要打你） 事件先后顺序是 事件A -> 事件B 对吧？ 对于有先后关系的，可以用图表示 例如1要在2前 可以从2建一个入度（单向边，从1指到2） 这样你只有访问到1才能访问到2 保证 1前2后 以此类推

有环

还是刚刚的例子 你妈高兴的要打你，但是你要喝可乐 事件A 你要喝可乐，喝完你妈才能打你 事件B 你妈要先打你，打完再喝

就有 事件A <-> 事件B 两件事无法排序了？

如上述关系的在图中称为 环 这叫做 相互依赖

那该怎么写？

基本思路：

1.当然先建图啦！

谁在前就谁向另一项连边 示例: (全部都是 A -> B)

//文件头省略哈
const int maxn = 1000 + 10; // 规定图范围
vector<int> G[maxn]; //此处中括号表示动态数组内的单独数组，类似于二维数组
int ru[maxn]; //记录每个点的入度；

// 省略中间 直击主题
// 假设我们输入了一组数据 a,b，要求 a 在 b 前
G[a].push_back(b); // a的出度(有向边) 出向b
ru[b]++; // b的入度加1；

2.开始

这个特性与queue相似，所以用queue实现较为容易

//那肯定先枚举ru数组内 看有没有0的，如果有0，说明他是第一个元素，加入queue内
queue<int> que;
for(int i=1;i<=ml;i++){
        if(ru[i] == 0){
            que.push(i);
        }
    }
//这样就得到第一个数啦

3.删边与完善

//既然得到了开头，那就继续处理啦
while(!que.empty()){ //队列不空就证明还有不是环的成员
        int now = que.front(); //取队首
        que.pop(); //弹出
        for(auto it : G[now]){ //枚举这个弹出元素的出度
            ru[it]--; //这个元素弹掉了，那原本入度包含这个元素的元素入度就要减1嘛
            if(ru[it] == 0){ //判断，入度为0证明下一个开头是他
                que.push(it); //入队
            }
        }
    }

写法总结

关键点解析 入度（inDegree）：指向该节点的边数量

入度为0的节点可以作为拓扑排序的起点

算法流程：

不断移除入度为0的节点

更新剩余节点的入度

重复直到所有节点被处理或发现环

环检测：

如果最终结果包含的节点数 < 总节点数 → 存在环

因为环中的节点入度永远不会降为0

时间复杂度：O(V+E)

每个节点和边只被处理一次

此说明仅为拓扑入门，若有疑问/错误,可以指出