Bridges & articulation points

Find single points of failure. Removing a bridge increases the number of components; removing an articulation vertex does too.

Prerequisites: Basic C++ input/output, vectors, loops, and the preceding graph lessons.

Build the idea

1. Record entry time tin[v] and lowest reachable ancestor time low[v].
2. After a DFS child u returns, update low[v] using low[u].
3. The tree edge v–u is a bridge when low[u] > tin[v].
4. A nonroot v is an articulation point when a child has low[u] ≥ tin[v]. A root needs more than one DFS child.
5. tin[v] is discovery time and low[v] is the earliest ancestor reachable from its DFS subtree through a back edge. Skip the parent edge ID, not the parent vertex, so parallel edges remain valid alternate routes. The root articulation condition is separate.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    // Undirected adjacency: (neighbor, unique edge id).
    vector<vector<pair<int,int>>>g(n+1);
    vector<int>tin(n+1,-1),low(n+1);
    vector<bool>cut(n+1);
    for(int id=0;id<m;id++){
        int a,b;
        cin>>a>>b;
        g[a].push_back({b,id});
        g[b].push_back({a,id});
    }
    int timer=0;
    vector<int>bridges;
    function<void(int,int)>dfs=[&](int v,int parentEdge){
        tin[v]=low[v]=timer++;
        int children=0;
        for(auto[u,id]:g[v]){
            if(id==parentEdge){
                continue;
            }
            if(tin[u]!=-1){
                low[v]=min(low[v],tin[u]);
            }
            else{
                dfs(u,id);
                ++children;
                low[v]=min(low[v],low[u]);
                if(low[u]>tin[v]){
                    bridges.push_back(id);
                }
                if(parentEdge!=-1&&low[u]>=tin[v]){
                    cut[v]=true;
                }
            }
        }
        if(parentEdge==-1&&children>1){
            cut[v]=true;
        }
    };
    for(int v=1;v<=n;++v){
        if(tin[v]==-1){
            dfs(v,-1);
        }
    }
    vector<bool>isBridge(m,false);
    for(int id:bridges){
        isBridge[id]=true;
    }
    cout<<bridges.size()<<'\n';
    bool firstBridge=true;
    for(int id=0;id<m;id++){
        if(isBridge[id]){
            if(!firstBridge){
                cout<<' ';
            }
            cout<<id+1;
            firstBridge=false;
        }
    }
    cout<<'\n';
    vector<int>cuts;
    for(int vertex=1;vertex<=n;vertex++){
        if(cut[vertex]){
            cuts.push_back(vertex);
        }
    }
    cout<<cuts.size()<<'\n';
    for(int i=0;i<(int)cuts.size();i++){
        if(i>0){
            cout<<' ';
        }
        cout<<cuts[i];
    }
    cout<<'\n';
}

Complexity analysis

O(V + E) time and space.

Example input and output

Read n m and m undirected edges, numbered 1..m in input order. Require 1≤n≤2000 for recursive DFS. Print bridge count, sorted bridge IDs, articulation-point count, and sorted vertex labels on four lines. Empty lists use blank lines.

Input

5 5
1 2
2 3
3 1
3 4
4 5

Output

2
4 5
2
3 4

The triangle has alternate routes. Edges 4 and 5 are bridges; removing vertex 3 or 4 disconnects the graph.

Practical applications

Use low-link DFS to identify single-edge or single-vertex failures in undirected networks.

Check your understanding

Which condition identifies a bridge to DFS child u?

Put it into practice

Report all roads whose removal disconnects part of a network.