An edge $$e = uv$$ of a connected graph $$G$$ is called a bridge if $$G - e$$ is disconnected (obviously it increases the number of components)

## Undirected graph

In the following undirected graph $$G$$ the edges $$v_2v_3$$ and $$v_3v_4$$ are bridges

• An edge $$e$$ of an undirected graph $$G$$ is a bridge if and only if $$e$$ lies on no cycle of $$G$$
• Every edge of an undirected tree is a bridge

Let $$G$$ be an undirected graph, by analyzing the properties of the dfs tree we can determine if an edge is a bridge given the following facts:

• let $$u$$ and $$v$$ be two vertices of the dfs such that $$u$$ is an antecesor of $$v$$, also $$u$$ and $$v$$ are not adjacent
• if there's a back edge $$vu$$ then none of the edges in the $$u-v$$ path are bridges, if we remove one of them the graph is still connected because of this edge
• otherwise the edge is a bridge

### Implementation notes

• to check if a succesor of a vertex $$u$$ has a back edge to a predecessor of $$u$$ an additional state is stored in each vertex which is the discovery time of the lowest back edge of a successor of $$u$$ (by lowest back edge we mean the back edge to a vertex with the lowest discovery time) denoted as $$u_{back}$$, initially this state is set to the discovery time of the vertex $$v$$ i.e. $$u_{back} = u_{in}$$, this state is propagated when the backtracking is performed
• let $$uv$$ be a back edge, when this edge is analyzed the $$v_{back}$$ state needs to be updated to be the minimum between the existing $$v_{back}$$ and the discovery time of $$u$$, i.e. $$v_{back} = min(v_{back}, u_{in})$$
• let $$v$$ be an adjacent successor of $$u$$ in the dfs tree, when we've finished analyzing the branch of the tree because of the $$uv$$ edge we have to check if the $$v_{back}$$ state contains a back edge to some predecessor of $$u$$ ($$v_{back}$$ is propagated) i.e. $$u_{in} > v_{back}$$, if so then $$uv$$ is not a bridge
int time_spent;

// the adjacency list representation of G
vector<vector<int> > g;
// the time a vertex i was discovered first
vector<int> time_in;
// stores the discovery time of the lowest predecessor that vertex i's
// succesor vertices can reach **through a back edge**, initially
// the lowest predecessor is set to the vertex itself
vector<int> back;
// the bridges found during the dfs
vector<pair<int, int> > cut_edge;

void dfs(int v, int parent) {
// the lowest back edge discovery time of v is
// set to the discovery time of v initally
back[v] = time_in[v] = ++time_spent;

for (int i = 0; i < g[v].size(); i += 1) {
int next = g[v][i];

if (next == parent) {
continue;
}

if (time_in[next] == -1) {
dfs(next, v);
// if there's a back edge between a descendant of next and
// a predecessor of v then next will have a lower back edge discovery time
// otherwise it's a bridge
if (back[next] > time_in[v]) {
cut_edge.push_back(pair<int, int> (v, next));
}
// propagation of the lowest back edge discovery time
back[v] = min(back[v], back[next]);
} else {
// *back edge*
// update the lowest back edge discovery time of v
back[v] = min(back[v], time_in[next]);
}
}
}

/**
* Finds the bridges in an undirected graph G of order n and size m
*
* Time complexity: O(n + m)
* Space complexity: O(n)
*/
void bridges() {
int n = g.size();
time_spent = 0;
time_in.assign(n, -1);
back.assign(n, -1);
cut_edge.clear();

for (int i = 0; i < n; i += 1) {
if (time_in[i] == -1) {
dfs(i, -1);
}
}
}


## Directed graph (strong bridges)

Let $$G$$ be a directed graph, an edge $$uv \in E(G)$$ is a strong bridge if its removal increases the number of stronly connected components of $$G$$

The following is a connected graph $$G$$, every edge but $$v_2v_0$$ is a strong bridge because removing it from $$G$$ increases the number of strongly connected components, removing $$v_2v_0$$ doesn't increase the number of strongly connected components so it's not a bridge

A trivial algorithm to find the strong bridges of a digraph $$G$$ of order $$n$$ and size $$m$$ is as follows:

• Compute the number of strongly connected componentes of $$G$$ denoted as $$k(G)$$
• For each edge $$e \in E(G)$$
• remove $$e$$ from $$G$$
• compute the number of strongly connected components of $$G$$ denoted as $$k(G - e)$$
• if $$k(G) < k(G - e)$$ then $$e$$ is a bridge

The time complexity of the algorithm above is clearly $$O(m(n + m))$$

Let $$uv$$ be an edge of a digraph $$G$$, we say that $$uv$$ is redundant if there's an alternative path from vertex $$u$$ to vertex $$v$$ avoiding $$uv$$, otherwise we say that $$uv$$ is not redundant, computing the strong bridges is equivalent to compute the non-redundant edges of a graph

http://www.sofsem.cz/sofsem12/files/presentations/Thursday/GiuseppeItaliano.pdf