我想将一个有向无环图分解成最小数量的组件，这样在每个组件中，以下属性都是真的-
对于组件中的所有顶点对（u，v），都有一条从u到v或从v到u的路径。
这有什么算法吗？
我知道，当or被替换时，在这种情况下，它与查找强连接组件的数量（可以使用DFS）是相同的。
*编辑：*如果有向图包含循环（即它不是非循环的），会发生什么？
最佳答案
我的想法是使用dfs在拓扑上对图进行o（n）排序，然后考虑这个属性可能是假的哪些顶点。对于从两个不同分支连接或拆分为两个不同分支的用户，这可能是错误的。
我将从任何起始顶点（拓扑顺序中最低的）开始，沿着它的路径进入随机分支，直到您无法进一步从图（第一个组件）中删除该路径。这将重复，直到图为空，并且您拥有所有这些组件。
这看起来像一个贪婪的算法，但是考虑到你在第一次运行中发现了一条很短的路径（通过随机的坏运气），或者你找到了一条最长的路径（好运）然后在算法的另一个步骤中，您仍然需要找到那个小分支组件。
复杂性是O（n个组成部分）。
当存在和条件时，应该考虑任何有向图，因为DAG不能具有强连接组件。
关于algorithm - 有向图分解，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33606608/