在我开始之前，是的，这是一个家庭作业。如果我在过去 14 小时内没有尽我所能解决这个问题并且一无所获，我就不会在这里发帖。
问题如下：我想检查是否可以在 O(V) 时间内从连接的无向图中删除一条边而不断开它，而不仅仅是线性的。
到目前为止我所达到的：
可以在不断开图形的情况下删除循环边缘，因此我只需检查图形是否有循环。我有两种方法可以使用，一种是 DFS，然后检查我是否有后边缘；另一种是通过计算 Vs 和 Es 并检查是否 |E| = |V| - 1，如果这是真的，那么图是一棵树，没有节点我们可以在不断开连接的情况下删除它。
前面的两种方法都解决了这个问题，但都需要 O(|E|+|V|)，而且书上说有一种更快的方法（这可能是一种贪婪的方法）。
请问我可以得到任何提示吗？
编辑：更具体地说，这是我的问题；给定一个连通图 G=(V,E)，我可以删除 E 中的一些边 e 并且结果图仍然是连通的吗？
图形的任何递归遍历，在节点被访问时标记节点，如果遇到已经标记的节点，则短路以返回 true 将起到作用。如果没有可以删除的边，这需要 O(|V|) 遍历整个图，如果提前停止返回 true，则需要更少的时间。
编辑
是的，整个图的递归遍历需要 O(|V|+|E|) 时间，但我们只在没有循环的情况下遍历整个图——在这种情况下 |E| = |V|-1 并且只需要 O(|V|) 时间。如果有一个循环，我们最多遍历|V| 后找到它。边（最多访问 |V|+1 个节点），这同样需要 O(|V|) 时间。
此外，显然当从一个节点（不是第一个节点）遍历时，您不会考虑您用来到达该节点的边，因为这会导致您立即看到一个已经访问过的节点。
您列出所有边 E 并取一条边并一一标记所访问的两端顶点。如果在遍历过程中我们发现这两个顶点之前已经被一些边访问过，我们可以删除该边。
我们最多只能靠边|V| 是时候看看这个条件是否满足了。
最坏的情况可能是这样的，每次我们采取边缘时，它都会访问至少一个新的顶点。然后有|V| 顶点，我们必须取 |V| 要找到该特定边的边。
最好的情况可能是带有 |V| 的情况。/ 2 + 1 e
你听说过跨树吗？具有 V-1 条边的连通图。
我们可以从连通图 G 中删除某些边（比如创建循环的边），直到我们得到一棵连通树。请注意，该问题并不是要您找到生成树。
问题是询问您是否可以在不丢失连接性的情况下从图中删除一条或多条边。只需计算边数并在计数超过 V-1 时中断，因为该图具有删除更多边并成为生成树的范围。如果图形在邻接表中给出，则可以在 O(V) 时间内完成。
根据我的阅读，没有重复的 DFS 被认为是 O(|V|)，所以如果你取边 e，让它连接的两个顶点是 u 和 v，如果你从 u 运行 DFS，忽略 e，你可以假设如果发现 v，则 e 不是桥，并且假设没有重复的 DFS 是 O(|V|)，那么我想这将被认为是 O(|V|)。