graph-algorithm - 计算有根 DAG 中最大路径等效节点的类

Question

我有一个带有单个根节点 r 的有根有向无环图。我对计算以下等价物感兴趣：

“节点 v 和 w 是最大路径等价的，如果来自 r 的每个最大路径都包含 v 和 w 或者都不包含它们”

特别是，我想在上述条件下找到所有等价类，可能在 O(n+m) 时间内（n 个节点，m 个边）。我觉得这个问题不是未知数，但我不知道要搜索什么术语。如果有人知道这个问题被称为什么或对如何解决它有任何想法，我将不胜感激。

标签： graph-algorithmdirected-acyclic-graphsequivalence