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:
This is a companion discussion topic for the original entry at http://iq.opengenus.org/find-cut-edges-in-a-graph/