Graph Theory37 sections · 1633 units
Open in Course

Building 2-Edge-Connected Components

(Contract non-bridge edges)

1.1. Find all bridges using Tarjan's algorithm.

2.2. Remove bridges from the graph (conceptually, do not modify the original).

3.3. Each connected component in the remaining graph is a 22-edge-connected component.

Run DFS or BFS on the bridge-removed graph to identify components. Vertices in the same component have no bridges between them, meaning they remain connected even if any single edge fails.