[Note] 拓扑排序

拓扑排序

1. 生态位

• 识别：

  1. 依赖关系: 任务 A 必须在 任务 B 之前完成（前驱后继）。其实依赖关系我觉得也可以理解为一种偏序关系吧。

  2. 环路检测: 判断一个有向图是否存在环。

  3. 序的贪心: 在满足依赖的前提下，要求编号小的尽可能靠前。

• 地位：DAG 上的基本工具。它是将复杂的网状依赖转化为线性序列的模型工具，也是在 DAG 上进行 DP 的前置序。

• 用途：依赖问题、DAG 最长路/最短路、以及判定图的死锁（环）。

2. 逻辑支点

2.1 核心原理：剥洋葱

拓扑排序的物理本质是不断移除没有依赖的节点。

• 入度: 入度为 0 表示该节点无依赖。

• 队列: 存放当前所有无依赖的节点。

2.2 模型

• Kahn 算法 (BFS):

  • 维护入度数组。初始将所有入度为 0 的点入队。

  • 每次取出一个点 $u$，将其所有邻居 $v$ 的入度减 1。若 $v$ 入度归零，则入队。

  • 性质: 如果最后输出的点数 $< N$，说明图中有环。

• 字典序贪心:

  • 原理: 将 Kahn 算法中的 queue 替换为 priority_queue。

  • 效果: 在每次有多个“自由”节点可供选择时，优先选择编号最小（或最大）的节点，从而保证生成的拓扑序列具有最小（或最大）字典序。

• DAG 最长路 (DP 序):

  • 拓扑序其实就是 DP 的状态转移顺序。

  • $dist[v] = \max(dist[v], dist[u] + 1)$。

3. 实战部署

▶

Kahn Topological Sort

const int maxn = 1e5 + 50;

vector< int > adj[maxn];
int indeg[maxn];
int seq[maxn]; // 存储拓扑序结果
int n, m;

bool toposort( )
{
    // 如果要求字典序最小，将 queue 换成 priority_queue 并使用 greater
    queue< int > q;
    
    // 1. 初始化：入度为 0 的点入队
    for( int i = 1; i <= n; ++ i )
    {
        if( indeg[i] == 0 ) q.push( i );
    }

    int cnt = 0;
    while( !q.empty( ) )
    {
        int u = q.front( );
        q.pop( );
        seq[++ cnt] = u;

        // 2. 剥离依赖
        for( auto v : adj[u] )
        {
            indeg[v] --;
            if( indeg[v] == 0 ) q.push( v );
        }
    }

    // 3. 判环：如果出队的点少于 n，说明有环
    return cnt == n;
}

4. 知识关联

• 母题: P1038 神经网络 —— 模拟 DAG 上的信号传递，很纯粹的拓扑模型。

• 实战案例:

  • 隐式图与最长路: P1983 车站分级 (未停靠 < 停靠 $\implies$ 偏序关系)。

  • 逆向思维: P3243 菜肴制作 (特定位置贪心，反向建图 + 拓扑)。

• 关联笔记:

  • [[差分约束]] —— 拓扑排序可以视为差分约束的一种特例（只存在 $A < B$ 的刚性约束）。