algorithm - 来自几个强连通分量的连通子图

Question

假设，给定一个连通的有向图 G，其中有几个强连通的分量:G1，G2，...所有这些都是已知的，并且有一个函数 f : Gi -> bool 对其中一些返回 true和其他人的虚假。

现在让我们获取所有 Gi，使得 f(Gi) 为真并忽略其他。是否有一些简单的方法可以在 G 中构建连接的子图，包含所有子图，以及 G 中最少数量的其他边？

Answer 1

进行缩合，然后在该缩合的子图f(Gi) = true 中生成生成树。提示，凝聚总是部分有序的，这使得生成树的构建更容易。