Bridges

#include<bits/stdc++.h>
#define ll long long

struct Bridge 
{
    // NOTE:
    //      vertices are ZERO-BASED index
    //      UN-DIRECTIONAL GRAPH
    int n;
    vector< vector<int> > adj;
    vector< vector<int> > edge_idx;
    vector<int> bridges;
    int *num;
    int *low;
    int cnt;
    
    void init(int n_) {
        n = n_;
        
        adj.clear();
        adj.resize(n+1);
        
        edge_idx.clear();
        edge_idx.resize(n+1);
        
        bridges.clear();
        
        num = new int[n+1];
        low = new int[n+1];
        for (int i = 0; i <= n; ++i)
            num[i] = low[i] = -1;
            
        cnt = 0;
    }
    
    void addEdge(int u, int v, int idx) {
        adj[u].push_back(v);
        adj[v].push_back(u);
        
        edge_idx[u].push_back(idx);
        edge_idx[v].push_back(idx);
    }
    
    void dfs_bridge(int u, int pa) {
        num[u] = low[u] = ++cnt;
        
        for (int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i];
            
            if (v == pa)
                continue;
            
            if (num[v] < 0) {
                dfs_bridge(v, u);
                low[u] = min(low[u], low[v]);
                
                if (low[v] >= num[v]) {
                    bridges.push_back(edge_idx[u][i]);
                }
            }
            else {
                low[u] = min(low[u], num[v]);
            }               
        }
        
    }
    
    vector<int> findBridges() {
        for (int i = 0; i < n; ++i)
            if (num[i] < 0)
                dfs_bridge(i, -1);
        
        return bridges;
    }
    
};