我试图解决在线法官的问题。给定一个有 n 个顶点（<=50000）的无向图，最初没有边，然后给定 m 个边（<100000），并且我们被要求在每次添加后输出桥的数量。时间限制为2s。我知道在 O(N + M) 中运行的桥梁查找算法，并且我的直接 O(M*(N+M)) 可以预见地超时。有人可以帮我一个合适的算法吗？
谢谢。
问问题
764 次
1 回答
1
岛屿是节点的集合，因此您可以从一个节点穿越到另一个节点而无需跨越任何桥梁。未连接到任何其他节点的单个节点是一个孤岛。
岛链是由桥梁连接的一系列岛屿。岛链是无环的；如果您通过一座桥离开岛屿，则只能通过同一座桥返回该岛。请注意，这与说组成岛链的节点集合是非循环的不同；个别岛屿可能包含循环。
在向图添加边时，请遵循以下规则来跟踪您的链、岛和桥：
如果添加了一条新边将一个岛连接到自身，则该边不是桥。桥梁总数保持不变。
如果两个岛不是同一个岛链的一部分，并且添加了一条连接它们的新边，那么这条边就变成了一座桥，两个岛链合并成一个岛链。
如果两个岛是岛链的一部分，并且添加了一条连接它们的新边，则必须合并一些岛以维护无环属性。找到通过连接两个岛屿的岛链的路径。以这种方式穿越的所有岛屿，包括两端的两个岛屿，将它们全部合并为一个岛屿。你以这种方式穿越的任何桥梁都不再成为桥梁。
通过这些步骤，您可以在向图中添加边时计算图中的桥梁数量。从未连接节点的图表开始。每个节点是一个岛链，其中包含一个岛，其中包含一个节点。添加边时，请参考上述三个规则，根据需要合并岛和岛链。
一个岛可以表示为一组节点，一个岛链可以表示为一个无向无环岛图。该算法最昂贵的部分是找到两个现有岛屿之间的路径；直观地说，我猜一个链中的岛屿数量相对于 将保持较小n，因此总复杂度将保持接近 O(m) 时间。
于 2012-07-19T16:55:23.730 回答