已知连通DAG中某作业开始时间，如何计算所有作业的开始时间？

核心约束推导 #

首先明确题目两个条件结合后的关键等式：
对于任意边 u → v（u是v的父作业），必须满足 start[v] = start[u] + duration[u]。
推导依据：

• 有父作业的v需尽早启动，因此start[v] ≥ start[u] + duration[u]；
• u完成后与v启动不能有间隔，因此start[v] ≤ start[u] + duration[u]；
  两者结合只能取等号。

对于有多个父节点的v，所有父节点u的start[u] + duration[u]必然相等（题目保证条件可满足），因此start[v]就是这个公共值。

高效计算步骤 #

已知目标节点target的开始时间S，通过两次拓扑相关遍历即可计算所有节点的start时间：

1. 正向拓扑遍历（处理target的下游节点）

   • 初始化start[target] = S。
   • 按拓扑顺序（父节点优先于子节点）遍历所有节点：
     • 对当前节点u，遍历其所有子节点v：
       • 直接通过等式计算start[v] = start[u] + duration[u]。
       • 题目已保证条件合法，无需处理冲突（若出现冲突则输入不合法）。

2. 逆拓扑遍历（处理target的上游节点）

   • 先构建反向图：将所有原边u→v反转成v→u。
   • 按逆拓扑顺序（子节点优先于父节点，即反向图的拓扑顺序）遍历所有节点：
     • 对当前节点v，遍历其所有原父节点u（即反向图中的子节点）：
       • 通过等式变形计算start[u] = start[v] - duration[u]。
       • 同样，题目保证无冲突。

示例验证 #

针对题目给出的例子：

• 图结构：A→C、B→C，duration[A]=3，duration[B]=1，已知start[A]=0。
• 正向遍历：
  处理节点A，计算得到start[C] = 0 + 3 = 3。
• 逆拓扑遍历（顺序为C→B、C→A，A已初始化）：
  处理节点C，计算得到start[B] = 3 - 1 = 2。
  最终结果与示例完全一致：start[B]=2，start[C]=3。

时间复杂度 #

整个流程的时间复杂度为O(N + E)，其中N是节点数，E是边数：

• 拓扑排序和逆拓扑排序的时间均为O(N + E)；
• 两次遍历的时间也为O(N + E)。
  这是DAG问题的最优时间复杂度。

内容的提问来源于stack exchange，提问作者Simd