我想将有向无环图分解为最少数量的组件，以便在每个组件中满足以下属性 - 对于组件中的所有顶点对 (u,v)，存在从 u 到 v 或从 v 到 u 的路径。
有什么算法吗？
我知道当条件中的 or 被替换为 and 时，它与查找强连通分量的数量相同(这可以使用 DFS)。
*编辑:*如果有向图包含循环(即它不是非循环的)会怎样？
最佳答案
我的想法是使用 DFS 以 O(n) 的拓扑方式对图进行排序，然后考虑对于哪些顶点此属性可以为假。对于从 2 个不同分支加入或拆分为 2 个不同分支的人来说，这可能是错误的。
我会从任何起始顶点(拓扑排序中最低的)开始并沿着它的路径进入随机分支，直到你不能走得更远并从图中删除这条路径(第一个组件)。这将重复直到图为空并且您拥有所有这些组件。
这似乎是一个贪心算法，但考虑到您在第一次运行时找到了一条非常短的路径(运气不好)或者您找到了一条最长的路径(运气好)。然后你仍然需要在算法的另一步中找到那个小分支组件。
复杂度为 O(n*组件数)。
当存在和条件时，您应该考虑任何有向图，因为 DAG 不能具有强连通分量。
关于algorithm - 有向图分解，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33606608/