在有向图中求强连通分量SCC并缩点后将缩点得到的每个强连通分量按 ‌Tarjan算法中的完成时间戳finish time递减顺序排列‌恰好构成该DAG的拓扑序。其核心原因在于 ‌Tarjan算法的DFS遍历性质与拓扑排序的定义完全一致‌。‌理论基础与关键性质‌‌强连通分量缩点后形成DAG‌任意两个强连通分量之间至多存在单向边否则它们应属于同一SCC因此缩点后的图必为有向无环图DAG。‌Tarjan算法的时间戳定义‌在DFS过程中为每个节点 u 维护两个时间戳dfn[u]首次访问 u 的时间戳进入时间。low[u]从 u 出发能回溯到的最小 dfn 值可到达的最早祖先。当 dfn[u]low[u] 时说明 u 是当前SCC的根节点此时弹出栈中所有属于该SCC的节点并分配一个递增的SCC编号scc_cnt。‌关键性质边的方向与完成时间戳的关系‌若存在一条从节点 u 到 v 的边u→v则在Tarjan算法的DFS中若 v 未被访问 → v 是 u 的后代u 的完成时间戳 v 的完成时间戳。若 v 已被访问且在栈中 → u 和 v 同属一个SCC不影响缩点。若 v 已被访问且不在栈中 → v 属于已处理的SCC此时 u 的完成时间戳 v 的完成时间戳。‌结论对任意边 u→v总有 finish[u]finish[v]‌。‌SCC编号与完成时间戳的映射关系‌Tarjan算法中SCC编号 id[u] 是按 ‌完成时间戳递增顺序‌ 分配的先完成的SCC编号小后完成的SCC编号大。因此‌SCC编号递减的顺序 完成时间戳递减的顺序‌。‌拓扑序的定义与一致性验证‌拓扑排序要求对DAG中任意边 A→B在排序中 A 必须出现在 B 之前。设缩点后存在边 SCCi​→SCCj​则原图中必有边从 SCCi​ 中某节点指向 SCCj​ 中某节点。由上述性质finish[SCCi​]finish[SCCj​]。故在按完成时间戳‌递减‌排序时SCCiSCCi​ 排在 SCCjSCCj​ 前面 → ‌满足拓扑序要求‌。‌结论‌‌将缩点后的DAG节点按Tarjan算法中的完成时间戳递减排序等价于按SCC编号递减排序该顺序天然满足所有边从左到右的约束因此是合法的拓扑序。‌这一结论是Tarjan算法的‌内在性质‌无需额外排序直接按出栈顺序的逆序即SCC编号递减即可获得拓扑序。