将一个有向无环图(DAG)分解成多个组件，然后在这些组件中找到根和最后一个子组件

Question

我想把一个图分成它的组件（就像下面的例子DAG一样。注意每个节点的有色标识符，因为它们代表组件）。在我找到图片中的组件后，我希望找到该组件的根和最后一个子组件。以蓝色组件为例，根是E，最后一个子是H。绿色：根b-最后一个子h。

如果您可以在E-H、B-E、B-H、a-I之间找到连接，而无需将其拆分为组件。让我知道，因为这是我的最终目标。

关于组件的编译。那实际上是我的最终目标。我只是想把它包括进来，也许让你更好地理解我试图实现的目标。一旦我找到这些联系，这就不可能了。

我发现有帮助但没有回答我的问题的问题：

> 有向无环图中寻找最低公共祖先的

算法？

寻找两个叶节点的最佳共同祖先，其中节点有零个、一个或两个亲本

Answer 1

太长了，不能发表评论，但我不认为你找到了所有共同的祖先：

来自维基百科：

在图论和计算机科学中，树或有向无环图(DAG)中的两个节点V和W的最低共同祖先(LCA)是同时具有V和W作为后代的最低（即最深）节点，其中我们将每个节点定义为自己的后代（因此，如果V与W有直接联系，W就是最低共同祖先）。

如果考虑双亲的LCA，那么顶点H有4个双亲，它们是C、D、F和G，那么您可以将LCA视为任何双亲对的值：

• LCA(C，D)=b
• LCA(C，F)=C
• LCA(C，G)=C
• LCA(D，F)=D
• LCA(D，G)=D
• LCA(F，G)=E

因此，H父代的LCAs是B、C、D和E。

共同祖先将是最低级的共同祖先及其祖先--因此A、B、D和E。

您需要说明为什么A、C和D被排除为共同祖先。