给定一个有向图，如果两个节点之间有一条备用路径，则移除它们之间的边。例：给定a->b，b->c，a->c，删除a->c。是否有一个有效的算法来计算删除的边数？
最佳答案
来自wikiStrongly connected component：
有向图是非循环的当且仅当它没有具有多个顶点的强连通子图时，因为有向环是强连通的，并且每个非平凡的强连通分量至少包含一个有向环。
您可以使用Tarjan's strongly connected components algorithm查找scc。然后从每个组件中删除一条边。
接下来，需要迭代整个过程，因为每个非平凡的强连接组件至少包含一个有向循环。
一般来说，计数周期数是NP-难的，就像你可以在多项式时间内计数所有的周期，那么你也可以检测哈密顿圈的存在性。但是Hamiltonian path是NP难的。
关于algorithm - 删除有向图中的重复边，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50658506/