Finding bridges in a graph in O(N + M)

Problem Statement

Finding bridges in a graph in O(N + M) Problem Description We are given an undirected graph. A bridge is defined as an edge which, when removed, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all bridges in the given graph. Informally, the problem is formulated as follows: given a map of cities connected with roads, find all "important" roads, i.e. roads which, when removed, cause disappearance of a path between some pair of cities. The algorithm described here is based on depth first search and has O(N + M) complexity, where N is the number of vertices and M is the number of edges in the graph. Note that there is also the article Finding Bridges Online - unlike the offline algorithm described here, the online algorithm is able to maintain the list of all bridges in a changing graph (assuming that the only type of change is addition of new edges). Algorithm Pick an arbitrary vertex of the graph root and r