我必须从 BFS 或 DFS 设计一个算法来执行以下操作，给定 G=(V,E) 一个有向图：
检查是否存在从s到 V 中任何其他顶点 u 的至多一条简单路径。该算法必须在 O(|V|+|E|) 上。
并且从前面的算法中，我必须设计另一个 O(|V||E|) 算法来检查任意两个顶点u和v之间是否最多有一个简单路径。
我希望你能帮帮我！提前非常感谢！
问问题
761 次
1 回答
2
提示：如果从s到u的路径上的所有边都是切边（桥）怎么办？如果其中任何一个不是最先进的怎么办？:)
注意：我们可以在 O(V+E) 时间内找到所有的桥梁
于 2013-07-07T13:24:28.753 回答