描述一种算法，以确定在具有新边缘的新 DFS 运行 中是否可能出现相同的 discovery/finishing 次
Describe an algorithm to determine if the same discovery/finishing times are possible in a new DFS run with a new edge
给你一个有向图 G = (V,E) 和一个 DFS 森林，在 DFS 运行 之后每个顶点的 discovery/finishing 次。假设一个新的边 e 现在被添加到 G。旧的发现和完成时间在 O(1) 可用，描述一个有效的算法来确定相同的 discovery/finishing 时间在新的 DFS 运行 在 G'=(V,E+e).
首先，我认为如果 e 连接了 2 个以前未连接的组件，那么这是不可能的，因为在第一个之后发现的组件中的任何顶点的发现时间将晚于第一个的任何完成时间组件，不能再这样了。
接下来，我认为如果e进入的顶点u被e离开的顶点v发现，那么某个顶点的discovery/finish时间必须改变。虽然不确定如何证明这一点。
所以我认为 v 和 u 必须在同一棵树中并且 u.d < v.d，但我不确定，我想不出一种方法来 prove/disprove 它。
如果它是正确的，我想你可以检查是否有一个顶点 w 使得 d.w < d.v < d.w < f.w 来验证以上两个条件适用于 O(V) 时间。但是我感觉我走的路不对。
为了便于引用问题陈述中包含的元素，我们假设边被标记为 e，并且它连接两个顶点 u 和 v。我将任何顶点 w 的发现和完成时间分别称为 w.d 和 w.f。
根据 u 和 v 的发现和完成时间，有四种可能的计时情况。我相信如果每个这样的案例都单独考虑，答案就会很清楚。
首先，让我们考虑 u.d < v.d < v.f < u.f 的情况。如果 v 是初始图中 u 的子代或间接后代 G，则可以出现此顺序。在这种情况下，根据您存储和遍历图形结构的方式，添加 e 可能 会导致相同的发现和完成时间。换句话说，DFS 仍然可以先使用旧边，并以相同的 discovery/finish 次结束。 e 将仅作为额外的后退或前进边缘进行处理，这不会影响结果 discovery/finish 次。
第二种情况是u.d < u.f < v.d < v.f。在此设置中，将 e 添加到初始图后，由于 DFS 算法的穷举子优先处理策略，u 将有 v 作为直接子节点， v.d 和 v.f 值将更新为不可避免地小于 u.f。在这种情况下，不可能保留初始 discovery/finish 值，它们将被更改，无论它们是否在同一连接组件中。
第三种和第四种情况是前两种情况的反映，交换了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 的初始发现时间和完成时间。如果匹配第一种或第三种情况，那么加上e后的discovery/finish次可以还是一样。如果符合第二种或第四种情况，那么第二次DFS后时间肯定会改变运行.
由于无论图表的大小如何，您都在进行恒定数量的检查，因此该算法将花费 O(1) 时间并使用 O(1) 额外的 space.
给你一个有向图 G = (V,E) 和一个 DFS 森林，在 DFS 运行 之后每个顶点的 discovery/finishing 次。假设一个新的边 e 现在被添加到 G。旧的发现和完成时间在 O(1) 可用，描述一个有效的算法来确定相同的 discovery/finishing 时间在新的 DFS 运行 在 G'=(V,E+e).
首先，我认为如果 e 连接了 2 个以前未连接的组件，那么这是不可能的，因为在第一个之后发现的组件中的任何顶点的发现时间将晚于第一个的任何完成时间组件，不能再这样了。
接下来，我认为如果e进入的顶点u被e离开的顶点v发现，那么某个顶点的discovery/finish时间必须改变。虽然不确定如何证明这一点。
所以我认为 v 和 u 必须在同一棵树中并且 u.d < v.d，但我不确定，我想不出一种方法来 prove/disprove 它。
如果它是正确的，我想你可以检查是否有一个顶点 w 使得 d.w < d.v < d.w < f.w 来验证以上两个条件适用于 O(V) 时间。但是我感觉我走的路不对。
为了便于引用问题陈述中包含的元素，我们假设边被标记为 e，并且它连接两个顶点 u 和 v。我将任何顶点 w 的发现和完成时间分别称为 w.d 和 w.f。
根据 u 和 v 的发现和完成时间，有四种可能的计时情况。我相信如果每个这样的案例都单独考虑，答案就会很清楚。
首先，让我们考虑 u.d < v.d < v.f < u.f 的情况。如果 v 是初始图中 u 的子代或间接后代 G，则可以出现此顺序。在这种情况下，根据您存储和遍历图形结构的方式，添加 e 可能 会导致相同的发现和完成时间。换句话说，DFS 仍然可以先使用旧边，并以相同的 discovery/finish 次结束。 e 将仅作为额外的后退或前进边缘进行处理，这不会影响结果 discovery/finish 次。
第二种情况是u.d < u.f < v.d < v.f。在此设置中，将 e 添加到初始图后，由于 DFS 算法的穷举子优先处理策略，u 将有 v 作为直接子节点， v.d 和 v.f 值将更新为不可避免地小于 u.f。在这种情况下，不可能保留初始 discovery/finish 值，它们将被更改，无论它们是否在同一连接组件中。
第三种和第四种情况是前两种情况的反映，交换了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 的初始发现时间和完成时间。如果匹配第一种或第三种情况，那么加上e后的discovery/finish次可以还是一样。如果符合第二种或第四种情况，那么第二次DFS后时间肯定会改变运行.
由于无论图表的大小如何，您都在进行恒定数量的检查，因此该算法将花费 O(1) 时间并使用 O(1) 额外的 space.