给定一个有向图，如果两个节点之间存在替代路径，则删除它们之间的边。例如:给定 a->b、b->c、a->c，删除 a->c。是否有一种有效的算法来计算那些被移除的边的数量？
最佳答案
来自维基Strongly connected component :
A directed graph is acyclic if and only if it has no strongly connected subgraphs with more than one vertex, because a directed cycle is strongly connected and every nontrivial strongly connected component contains at least one directed cycle.
您可以使用 Tarjan's strongly connected components algorithm找到SCC。然后从每个组件中删除一条边。
接下来您需要迭代整个过程，因为每个非平凡强连通分量至少包含一个有向环。
一般而言，计算循环数是 NP-hard，因为如果您可以在多项式时间内计算所有循环，那么您也可以检测哈密顿循环的存在。但是Hamiltonian path是 NP 难的。
关于algorithm - 删除有向图中的重复边，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50658506/