Find Cut Edges in a graph


(Team) #1
A cut edge e = uv is an edge whose removal disconnects node u from node v.
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