Cla*_*ohn 4 algorithm tree big-o graph depth-first-search
给定一个连通图 G 和一系列边 S。每次从 S 中删除一条边，然后从 G 中删除一条边。然后检查 G 是否仍然连通。如果 G 不再连接，则返回该边。否则，您从图中删除边并继续。
我最初的想法是使用 Tarjan 的桥查找算法，该算法构建一棵 DFS 树，然后检查给定顶点是否有后边将其后代之一连接到它或其祖先之一。如果没有，那么它就是一座桥梁。
在构建树时，您可以在 O(V+E) 时间内找到所有桥，但我在调整 Tarjan 算法来解释删除时遇到问题。每次删除一条边时，树都会发生变化，并且我很难将算法保持在 O(V+E) 时间。有什么想法吗？
您可以在几乎线性的O(E * alpha(V))时间内相当轻松地完成此操作，其中 alpha 是增长极其缓慢的逆阿克曼函数，使用不相交集数据结构。诀窍是反转S并添加 Edge，因此您会询问何时G首次连接，而不是断开连接。增量连接问题比递减连接问题容易得多。
给定一种不相交集的实现，您可以对其进行扩充以跟踪组件的数量，并且当只有一个组件时，图会被精确连接。如果从组件开始n，那么在进行任何Union(x, y)操作之前，请检查x和是否y属于同一个组件。如果不这样做，则并集运算会将图的分量减 1。
对于您的图形，您需要进行预处理以查找 中 中 中 中不存在的S所有边，并首先将它们添加到不相交集数据结构中。然后，如果添加导致图第一次连接，则答案是，因为我们已经添加了。GSS[i]iS[i+1], S[i+2], ... S[n-1]
最佳复杂度
反阿克曼函数最多适用4于适合我们宇宙的任何输入，因此我们的并查算法通常被认为“几乎是线性的”。但是，如果这还不够好......
您可以在 中执行此操作O(V+E)，尽管它相当复杂，并且可能主要具有理论意义。Gabow 和 Tarjan 在 1984 年的论文中O(1)发现了一种算法，如果我们知道所有并集运算的顺序（我们在这里所做的），则该算法可以在每次操作的摊销成本中支持并查找。它仍然使用不相交集数据结构，但添加了额外的辅助结构来缓存小集合上的节点信息。
本文提供了一些伪代码，但您可能需要自己实现或在线查找实现。它也只适用于RAM 模型这个词，因为它从根本上依赖于在恒定时间内操作小位串以将它们用作查找表（一个相当标准的假设，但您需要进行一些低级位操作）。