Find all critical edges for minimum spanning tree This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne.


  4.3.26 Critical edges. An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to $E \log E$. Note: This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical).


There is an algorithm (see below), as well as an accepted answer, at stackoverflow.
However, in my opinion, the correctness proof is not complete because it does not justify that all critical edges can be found. Moreover, I cannot figure out how the time complexity of $O(m \log m)$ is achieved in this algorithm (given the hint in the answer).

The algorithm is (in my understanding):


Run Kruskal algorithm on this graph. Whenever we encounter an edge $e$ whose insertion in the MST creates a cycle, the edges in this cycle with smaller weights than $w(e)$ will be reported as critical edges.


My questions are:


How to prove the correctness of this algorithm: (1) all edges reported are critical edges; (2) all critical edges are reported?
How to achieve $O(m \log m)$ with appropriate data structures?
If this algorithm is wrong, how to solve the problem?
Since Kruskal's algorithm sorts the edges according to their lengths, the trick here i to partition the edges into subsets of edges with equal lengths.

For each subset (in increasing order) check which components are being joined using each edge of this set before joining them. If two (separate) components are being joined using more than one edge of this subset then both (all) these edges are non critical (since we can choose any of them and still get a spanning tree).

Now we are visiting each subset (and accordingly each edge) two times, the complexity is still in $O(|E|)$ and we need an additional $\log$ for the DSU join operations.

However, you should be aware of the case where for example three edges $\epsilon_1,\ \epsilon_2,\ \epsilon_3$ of the same lengths joins components $V_1-V_2, V_2-V_3, V_3-V_1$ respectively, which makes non of them critical point since we can use any two of them and leave the third one. A solution of this problem is to add all this edges at first to the Graph, then you will have a non tree graph, with cycles in places where you had many choices, and that makes the critical edges exactly the Bridges (check the link) in this graph.

P.S since bridges can be found in $O(|V| + |E|)$ total runtime is still $O(|E|*\log|E|)$