← all categories

Bridges 39a7ffb5

Tarjan bridge-finding via tin/low DFS, handles disconnected graphs. Returns the list of bridge edge indices, given adj[u] = {(v, edgeIndex), ...} listing both directions of each edge.

Time: O(V + E). tested

content/graphs/bridges.h

vector<int> findBridges(int n, vector<vector<pair<int, int>>> &adj) {
    vector<int> tin(n, -1), low(n), bridges;
    int timer = 0;
    auto dfs = [&](auto &&dfs, int u, int pe) -> void {
        tin[u] = low[u] = timer++;
        for (auto &[v, id] : adj[u]) {
            if (id == pe) continue;
            if (tin[v] != -1) {
                low[u] = min(low[u], tin[v]);
            } else {
                dfs(dfs, v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > tin[u]) bridges.push_back(id);
            }
        }
    };
    for (int i = 0; i < n; i++) if (tin[i] == -1) dfs(dfs, i, -1);
    return bridges;
}