向图中添加随机边时，哪些桥边不再是桥边？
When adding a random edge to a graph, which bridge edges are not bridge edges any longer?
一条随机边 e 被添加到图形中。它恰好不是桥边。设 C 为 e.
端点的连通分量
给定 L C 的所有桥边的列表（在 e添加），这是查找 L 中的哪些边在插入 e?
后仍然是桥接边的最快算法
如果允许预处理，有一个快速的方法：构造bridge-block forest，其顶点为2-连通分量，其边为桥。 （如果图是连通的，它就是一棵树。）当你添加一条边时，如果它连接了同一个 2-连通分量中的点，则什么也不会发生。如果您连接位于桥块森林的不同连接组件中的不同 2-连接组件中的点，则新边是一座桥（您假设不会发生）。如果将两个 2-connected 组件连接在同一个连接组件中，则找到这些 2-connected 组件之间的唯一路径。这些不再是桥梁，并且路径上的所有 2-connected 组件都收缩到一个新的 2-connected 组件。任何不在这条路上的桥仍然是一座桥。
有评论说你最多消除一座桥。这是不正确的。您可以连接桥块森林中的任意两点，包括任意距离的点。添加这样一条边会消除任意多条边。
在您的评论中，您提到了删除边。这可能什么都不做，但是如果你删除一个非桥接的 e，它可能会导致包含 e 的 2-connected 组件 C 进入任意长的路径，因此你需要重新计算 C 中的 2-connected 组件并将 C 替换为这条 2-连通分量的路径。将 C 连接到其他 2-连通分量的桥成为将新的 2-连通分量 C_!, ..., C_k 连接到 C 的邻居的桥。
一条随机边 e 被添加到图形中。它恰好不是桥边。设 C 为 e.
端点的连通分量给定 L C 的所有桥边的列表（在 e添加），这是查找 L 中的哪些边在插入 e?
后仍然是桥接边的最快算法如果允许预处理，有一个快速的方法：构造bridge-block forest，其顶点为2-连通分量，其边为桥。 （如果图是连通的，它就是一棵树。）当你添加一条边时，如果它连接了同一个 2-连通分量中的点，则什么也不会发生。如果您连接位于桥块森林的不同连接组件中的不同 2-连接组件中的点，则新边是一座桥（您假设不会发生）。如果将两个 2-connected 组件连接在同一个连接组件中，则找到这些 2-connected 组件之间的唯一路径。这些不再是桥梁，并且路径上的所有 2-connected 组件都收缩到一个新的 2-connected 组件。任何不在这条路上的桥仍然是一座桥。
有评论说你最多消除一座桥。这是不正确的。您可以连接桥块森林中的任意两点，包括任意距离的点。添加这样一条边会消除任意多条边。
在您的评论中，您提到了删除边。这可能什么都不做，但是如果你删除一个非桥接的 e，它可能会导致包含 e 的 2-connected 组件 C 进入任意长的路径，因此你需要重新计算 C 中的 2-connected 组件并将 C 替换为这条 2-连通分量的路径。将 C 连接到其他 2-连通分量的桥成为将新的 2-连通分量 C_!, ..., C_k 连接到 C 的邻居的桥。