有没有办法快速找无向环

1489题我的思路卡在了找无向环。。虽然最终看答案发现我的想法和答案真的是南辕北辙。。但还是想问问

就是在找mst的时候，不停union两个node嘛，然后，发现如果两个node的已经通过某些路径连起来了(find(x) == find(y))，就知道这个edge不应该加
但是，有办法知道形成这个环的edge有哪些么。。
我只能想到用dfs遍历整个图。但这样复杂度太高了。。有没有更快的办法么大佬们。。

DFS是O(V+E)应该已经是最快了的吧。

举个例子，整个图就是一个大环：A-B-C-D-...-A。
不把所有点和边都检查一遍就不知道到底有没有成环。

一个可能的优化是，如果边数量大于等于顶点数量，必然有环。所以可以声称DFS是O(V)的

usr_opta 发表于 2020/06/23 12:14:27
DFS是O(V+E)应该已经是最快了的吧。

我想的是 能不能在添加边的时候 就o1 update一个数据结构 因为每添加一个边 就要on一下 感觉堵在度略高。。
目前也觉得可能没办法哈哈