您将获得有向图G = (V,E)和DFS林，其中包含DFS运行后每个顶点的发现/完成时间。假设现在向G添加了新的边e。在O(1)处有旧的发现和完成时间，请描述一种有效的算法，以确定在G'=(V,E+e)上运行的新DFS中是否可以实现相同的发现/完成时间。
首先，我认为如果e连接了2个先前未连接的组件，那么这将是不可能的，因为在第一个组件之后发现的组件中任何顶点的发现时间将比第一个组件的完成时间晚。不再如此。接下来，我认为如果e进入的顶点u被e离开的顶点v发现，那么某些顶点的发现/完成时间必须改变。虽然不确定如何证明这一点。因此，我认为v和u必须在同一棵树中，并且u.d 如果正确，我认为您可以检查是否存在顶点w使得d.w
为了便于参考问题陈述中包含的元素，我们假设边被标记为e，并且它连接了两个顶点u和v。我将任何顶点w的发现和完成时间分别称为w.d和w.f。
u和v的发现和完成时间有四种可能的计时情况。我相信，如果单独考虑每种情况，答案将是清楚的。
首先，我们考虑u.d < v.d < v.f < u.f的情况。如果v是初始图形G中u的子代或间接子代，则可以发生此顺序。在这种情况下，取决于您如何存储和遍历图结构，添加e may会导致相同的发现和完成时间。换句话说，DFS仍然可以首先使用旧边缘，并以相同的发现/完成时间结束。然后，e将仅作为额外的后边缘或前边缘进行处理，这不会影响最终的发现/完成时间。
第二种情况是u.d < u.f < v.d < v.f。在此设置中，在将e添加到初始图形之后，由于u将以v作为直接子代，这归因于DFS算法的穷举子优先处理策略，v.d和[C0 ]值将被更新为不可避免地变得小于v.f。在这种情况下，不可能保留初始发现/完成值，并且无论它们是否在相同的连接组件中，它们都将被更改。
第三和第四种情况是前两种情况的反映，其中u.f和u互换了。 （即v和v.d < u.d < u.f < v.f）。您可以将前两种情况的说明也扩展到这些情况。
经过考虑，您要寻找的算法很难构建。您在v.d < v.f < u.d < u.f中拥有可用的发现和完成时间，并且看来您还知道O(1)连接的u和v顶点。您可以简单地检查e和u的初始发现和完成时间。如果它们匹配第一种或第三种情况，则添加v之后的发现/完成时间can仍然相同。如果它们与第二种或第四种情况匹配，那么第二次运行DFS后，时间肯定会改变。
由于无论图形大小如何，您都要进行恒定数量的检查，因此该算法将花费e时间并使用O(1)额外空间。