---
tags: Graph Theory
title: Bridge Finding
---

### Sample Code

vector<vector<int>> adj(n);
vector<bool> vis(n);
vector<int> times(n, -1), low(n, -1);

int count = 0;
int ans = 0;

function<void(int, int)> dfs = [&](int u, int p) {
    vis[u] = true;
    times[u] = low[u] = count++;
    for (int v : adj[u]) {
        if (v == p) continue;
        if (vis[v]) {
            low[u] = min(low[u], times[v]);
            continue;
        }

        dfs(v, u);
        low[u] = min(low[u], low[v]);
        if (low[v] > times[u]) ++ans;
    }
};

for (int i = 0; i < n; ++i) {
    if (!vis[i]) dfs(i, -1);
}

cout << ans << '\n';