Find Critical Connections in Network — Bridge Finding

from collections import defaultdict

def criticalConnections(n, connections):
    adj = defaultdict(list)
    for u, v in connections:
        adj[u].append(v)
        adj[v].append(u)

    disc = [-1]*n
    low = [0]*n
    bridges = []
    timer = [0]

    def dfs(u, parent):
        disc[u] = low[u] = timer[0]
        timer[0] += 1
        for v in adj[u]:
            if v == parent: continue
            if disc[v] == -1:
                dfs(v, u)
                low[u] = min(low[u], low[v])
                if low[v] > disc[u]:
                    bridges.append([u, v])
            else:
                low[u] = min(low[u], disc[v])

    dfs(0, -1)
    return bridges

function criticalConnections(n, connections) {
    const adj=Array.from({length:n},()=>[]);
    for(const[u,v]of connections){adj[u].push(v);adj[v].push(u);}
    const disc=new Array(n).fill(-1),low=new Array(n).fill(0);
    const bridges=[]; let timer=0;
    const dfs=(u,par)=>{
        disc[u]=low[u]=timer++;
        for(const v of adj[u]){
            if(v===par)continue;
            if(disc[v]===-1){dfs(v,u);low[u]=Math.min(low[u],low[v]);if(low[v]>disc[u])bridges.push([u,v]);}
            else low[u]=Math.min(low[u],disc[v]);
        }
    };
    dfs(0,-1); return bridges;
}

import java.util.*;
public List<List<Integer>> criticalConnections(int n,List<List<Integer>> conns){
    List<Integer>[]adj=new List[n]; for(int i=0;i<n;i++)adj[i]=new ArrayList<>();
    for(List<Integer>c:conns){adj[c.get(0)].add(c.get(1));adj[c.get(1)].add(c.get(0));}
    int[]disc=new int[n],low=new int[n]; Arrays.fill(disc,-1); int[]timer={0};
    List<List<Integer>>res=new ArrayList<>();
    dfs(0,-1,disc,low,timer,adj,res); return res;
}
void dfs(int u,int p,int[]disc,int[]low,int[]t,List<Integer>[]adj,List<List<Integer>>res){
    disc[u]=low[u]=t[0]++;
    for(int v:adj[u]){if(v==p)continue;if(disc[v]==-1){dfs(v,u,disc,low,t,adj,res);low[u]=Math.min(low[u],low[v]);if(low[v]>disc[u])res.add(List.of(u,v));}else low[u]=Math.min(low[u],disc[v]);}
}

#include <vector>
using namespace std;
int disc[100001],low[100001],t=0;
void dfs(int u,int p,vector<int>adj[],vector<vector<int>>&res){
    disc[u]=low[u]=t++;
    for(int v:adj[u]){if(v==p)continue;if(disc[v]==-1){dfs(v,u,adj,res);low[u]=min(low[u],low[v]);if(low[v]>disc[u])res.push_back({u,v});}else low[u]=min(low[u],disc[v]);}
}
vector<vector<int>> criticalConnections(int n,vector<vector<int>>&conns){
    vector<int>adj[n]; for(auto&c:conns){adj[c[0]].push_back(c[1]);adj[c[1]].push_back(c[0]);}
    fill(disc,disc+n,-1); vector<vector<int>>res; dfs(0,-1,adj,res); return res;
}

/* C: same DFS with disc/low arrays, iterative version for large n */