核心概述
适用于有向无环图的拓扑线性化与依赖顺序处理，提供 Kahn 与 DFS 两种实现以支持环检测与 DAG 上的序贯计算，时间复杂度 O(N+M)。
Description: Topologically sorts a directed graph (returns empty/partial if a cycle exists). Supports Kahn’s BFS (in-degree) or DFS with on-stack cycle detection. Time: O(N + M) Status: tested
-
接口（据实现）
- toposort(G) → order：若存在拓扑序则返回包含所有顶点的序列；若有环通常返回空序列或长度<N 的序列以示失败。
- G 为有向图，常用 0..N-1 索引，邻接表存边。
-
实现A：Kahn（入度队列）
- 预处理入度 in[v]，把所有 in[v]=0 的点入队。
- 反复出队 u：将 u 加入 order；对每条 u→v 令 in[v]—，若减为 0 则入队。
- 结束后若 |order|==N 则为合法拓扑序，否则图中存在环。
- 易于同时统计“可达层次/分批次序”等信息。
-
实现B：DFS（灰白黑/栈法）
- 维护 vis[v]∈{0,1,2} 或 onStack 标记；DFS 时若遇到 onStack 顶点，则检测到环，失败。
- 对每个未访问点做 DFS，回溯完成时把该点压入栈/序列，最终逆序即拓扑序。
- 常数小，实现紧凑；便于同时做 DAG DP。
-
输出语义
- order 是一个满足偏序约束的线性扩展；若存在环则无全覆盖的拓扑序。
- DAG 上常用：顺序扫描进行 DP（如最长路/路径计数/可达性传递等）。
-
复杂度
- O(N+M) 时间，O(N+M) 空间（与图存储一致）。
-
使用与注意
- 仅对 DAG 存在拓扑序；若不确定是否有环，可用 077-图论-强连通分量 先收缩成凝聚图再拓扑排序。
- 多个入度为 0 的候选点时，拓扑序不唯一；可使用优先队列得到字典序最小/最大拓扑序。
- 若需要判断唯一性，可检测每一步是否队列/堆中仅有一个可选顶点。