增量计算图中的网桥

Question

我试图解决网上法官的问题。给定一个n个顶点的无向图（< = 50000），最初没有边，然后给出m个边（<100000），并且我们被要求在每次加法后输出bridges的数量。时间限制是2秒。我知道在O（N + M）中运行的桥寻找算法，以及我的直接O（M *（N + M））超出预期。有人可以帮助我一个合适的算法？

谢谢。

Answer 1

岛是一个节点的集合，这样你就可以从一个节点遍历到另一个节点而不会跨越任何桥。没有连接到任何其他节点的单个节点是岛。

岛链是由桥梁连接的一系列岛屿。岛链是无环的;如果你通过一座桥离开一个岛，除了同一座桥，你不能回到岛上。请注意，这与组成岛链节点的集合是非循环的并不相同;个别岛屿可能包含循环。

当添加的边缘图表，遵循这些原则，让你的链条，岛屿，桥梁的轨道：

1. 如果一个新的边缘补充说，一个岛屿连接到本身，即边缘不是一座桥。桥梁总数保持不变。

2. 如果两个岛屿是不一样的岛链的一部分，一个新的边缘添加连接它们，那么边缘变成一座桥，这两个岛链合并成一个单一的岛链。

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

通过这些步骤，您可以在添加边缘的同时保持图形中桥接的数量。从未连接的节点开始。每个节点都是一个岛链，其中包含一个岛，其中包含一个节点。当您添加边缘时，请参阅上面的三条规则以根据需要合并岛屿和岛屿链。

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