Clearly such edges can be found in
O(m^2)
time by trying to remove all edges in the graph. We can get to O(m)
based on the following two observations:
* All cut edges must belong to the DFS tree.
* A tree edge uv with u as v’s parent is a cut edge if and only if there are no edges in v’s subtree that goes to u or higher.
Average case time complexity:
O(V+E)
; Space complexity: O(V)
This is a companion discussion topic for the original entry at http://iq.opengenus.org/find-cut-edges-in-a-graph/