algorithm - 递增地计算图中的桥

Question

我正在尝试解决在线法官的问题。给定一个有 n 个顶点(<=50000)的无向图，最初没有边，然后给定 m 条边(<100000)，我们被要求输出 bridges 的数量。每次添加后。时间限制为2s。我知道桥查找算法，它在 O(N + M) 中运行，而我的直截了当的 O(M*(N+M)) 超时可预见。有人可以帮我找到合适的算法吗？

谢谢。

Answer 1

岛屿是节点的集合，因此您可以从一个节点穿越到另一个节点而无需穿过任何桥梁。未连接到任何其他节点的单个节点是一个岛。

岛链是由桥梁连接的一系列岛屿。岛链是无环的；如果你通过一座桥离开一个岛，你只能通过同一座桥才能返回该岛。请注意，这与说构成岛链的节点集合是非循环的不同；个别岛屿可能包含循环。

向图中添加边时，请遵循以下规则来跟踪链、岛和桥:

1. 如果添加一条新边将岛连接到自身，则该边不是桥。桥梁总数保持不变。

2. 如果两个岛不属于同一个岛链，并且添加了一条连接它们的新边，那么这条边就变成了一座桥，两个岛链合并为一个岛链。

3. 如果两个岛是岛链的一部分，并且添加了连接它们的新边，则必须合并一些岛以维护非循环属性。找到穿过连接两个岛屿的岛链的路径。将这样遍历的所有岛屿，包括两端的两个岛屿，全部合并为一个岛屿。您以这种方式走过的任何桥梁都不再是桥梁。

通过这些步骤，您可以在向图中添加边时计算图中的桥数。从未连接节点的图形开始。每个节点都是一个岛链，其中包含一个单独的岛，其中包含一个单独的节点。添加边时，请引用上述三个规则，根据需要合并岛和岛链。

岛可以表示为一组节点，岛链可以表示为岛的无向无环图。该算法最昂贵的部分是找到两个现有岛屿之间的路径；直觉上，我猜测链中的岛数相对于 n 会保持较小，因此总复杂度将保持接近 O(m) 时间。