我想在网上法官那里解决一个问题给出一个n个顶点（bridges的数目。时间限制是2秒。我知道桥查找算法，它运行在o（n+m）中，并且我的直接o（m*（n+m））可预测地超时。有人能帮我找一个合适的算法吗？
谢谢。
最佳答案
孤岛是节点的集合，因此您可以在不跨越任何桥的情况下从一个节点遍历到另一个节点。没有连接到任何其他节点的单个节点是孤岛。
岛链是由桥梁连接起来的一系列岛屿。岛链是非循环的；如果你通过一座桥离开一个岛，你就不能回到岛上，除非通过同一座桥。请注意，这与构成孤岛链的节点集合是非循环的不同；单个孤岛可能包含循环。
向图形添加边时，请遵循以下规则来跟踪链、岛和桥：
如果添加了将孤岛连接到自身的新边，则该边不是桥。桥梁总数保持不变。
如果两个岛不属于同一岛链，并且添加了连接它们的新边，则该边将成为桥，并且两个岛链合并为一个岛链。
如果两个岛是岛链的一部分，并且添加了连接它们的新边，则必须合并其中一些岛以维护非循环属性。找到连接两个岛屿的岛链的路径。对于以这种方式穿越的所有岛屿，包括两端的两个岛屿，请将它们合并为一个岛屿。任何你以这种方式走过的桥都不再是桥。
通过这些步骤，可以在向图中添加边时统计图中的桥数。从未连接节点的图形开始。每个节点都是一个孤岛链，其中包含一个孤岛，其中包含一个节点添加边时，请参考上面的三条规则，以便根据需要合并孤岛和孤岛链。
一个岛可以表示为一组节点，一个岛链可以表示为岛的无向无环图。算法中最昂贵的部分是找到两个现有岛屿之间的路径；直觉上，我猜想链中的岛屿数量相对于n将保持较小，因此总的复杂性将保持接近O（m）的时间。
关于algorithm - 递增计数图中的桥，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/11564309/