Bridges and Articulation Points — Graph Vulnerability Detection

Definitions

Bridge: Edge (u,v) whose removal increases the number of connected components
Articulation Point: Vertex whose removal increases connected components

Both found in one DFS using disc[] and low[] arrays.

Bridge Condition

Edge (u→v) is a bridge if low[v] > disc[u] (v can't reach u without this edge).

Articulation Point Conditions

Root of DFS tree with 2+ children
Non-root u where low[v] >= disc[u] for some child v

Solutions

Python

def find_bridges_and_ap(n, adj):
    disc = [-1]*n
    low = [0]*n
    parent = [-1]*n
    bridges = []
    ap = set()
    timer = [0]

    def dfs(u):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        children = 0
        for v in adj[u]:
            if disc[v] == -1:
                children += 1
                parent[v] = u
                dfs(v)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append((u, v))
                if parent[u] == -1 and children > 1:
                    ap.add(u)
                if parent[u] != -1 and low[v] >= disc[u]:
                    ap.add(u)
            elif v != parent[u]:
                low[u] = min(low[u], disc[v])

    for i in range(n):
        if disc[i] == -1:
            dfs(i)
    return bridges, ap

JavaScript

function findBridgesAP(n, adj) {
    const disc=new Array(n).fill(-1),low=new Array(n).fill(0),par=new Array(n).fill(-1);
    const bridges=[],ap=new Set(); let timer=0;
    const dfs=(u)=>{
        disc[u]=low[u]=timer++; let children=0;
        for(const v of adj[u]){
            if(disc[v]===-1){
                children++; par[v]=u; dfs(v); low[u]=Math.min(low[u],low[v]);
                if(low[v]>disc[u])bridges.push([u,v]);
                if(par[u]===-1&&children>1)ap.add(u);
                if(par[u]!==-1&&low[v]>=disc[u])ap.add(u);
            }else if(v!==par[u])low[u]=Math.min(low[u],disc[v]);
        }
    };
    for(let i=0;i<n;i++)if(disc[i]===-1)dfs(i);
    return{bridges,ap:[...ap]};
}

Java

int[] disc,low,par; List<int[]> bridges=new ArrayList<>(); Set<Integer> ap=new HashSet<>(); int timer=0;
void dfs(int u,List<Integer>[]adj){
    disc[u]=low[u]=timer++; int ch=0;
    for(int v:adj[u]){
        if(disc[v]==-1){
            ch++;par[v]=u;dfs(v,adj);low[u]=Math.min(low[u],low[v]);
            if(low[v]>disc[u])bridges.add(new int[]{u,v});
            if(par[u]==-1&&ch>1)ap.add(u);
            if(par[u]!=-1&&low[v]>=disc[u])ap.add(u);
        }else if(v!=par[u])low[u]=Math.min(low[u],disc[v]);
    }
}

C++

int disc[100001],low[100001],par[100001],timer_=0;
vector<pair<int,int>> bridges; set<int> ap;
void dfs(int u,vector<int>adj[]){
    disc[u]=low[u]=timer_++; int ch=0;
    for(int v:adj[u]){
        if(disc[v]==-1){
            ch++;par[v]=u;dfs(v,adj);low[u]=min(low[u],low[v]);
            if(low[v]>disc[u])bridges.push_back({u,v});
            if(par[u]==-1&&ch>1)ap.insert(u);
            if(par[u]!=-1&&low[v]>=disc[u])ap.insert(u);
        }else if(v!=par[u])low[u]=min(low[u],disc[v]);
    }
}

C

/* C: same pattern — disc/low arrays, iterative DFS using explicit stack */