Today’s contest Div1 C—I didn’t know there was something called “biconnected components,” or that they could be found easily using bridges in O(n + m) (I should have studied that :( ). But I wrote this during the contest:

int n;
//LCA,DSU Templates
void solve() {
    int m;
    cin >> n >> m;

    DSU dsu(n + 1);   // DSU to merge nodes connected through cycles
    DSU dsu1(n + 1);  // DSU to build initial spanning tree
    vector<pair<int, int>> edges, nonTreeEdges;
    vector<int> dp(n + 1, 0);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        edges.push_back({a, b});
    }

    // Build initial spanning tree and separate back edges
    for (auto [u, v] : edges) {
        // dsu1.join returns true if u and v are in different components
        if (dsu1.join(u, v)) {
            adj[u].push_back(v);
            adj[v].push_back(u);
        } else {
            // back edges
            nonTreeEdges.push_back({u, v});
        }
    }
    build();
    // Builds binary lifting structure for LCA queries

    // The idea is just to connect all the nodes in the path from u to v on the tree
    for (auto [u, v] : nonTreeEdges) {
        int lca = LCA(u, v);
        int du = depth[u] - depth[lca];
        int dv = depth[v] - depth[lca];
        dp[u] = max(dp[u], du);
        dp[v] = max(dp[v], dv);
    }
    // DFS to propagate max distances and merge components for biconnected edges
    function<void(int, int)> dfs1 = [&](int v, int p) {
        for (auto u : adj[v]) {
            if (u == p) continue;
            dfs1(u, v);
            // If child has a back edge affecting it, merge it with parent
            if (dp[u]) dsu.join(u, v);
            // Propagate maximum distance upwards
            dp[v] = max(dp[v], dp[u] - 1);
        }
    };
    dfs1(1, -1);
    // After DFS, `dsu` connects all biconnected components correctly
    // This approach can be modified to work dynamically for online queries if the initial graph is connected
}

I had no idea why it worked though (it was just a feeling~) :) I treated each cycle independently, and somehow it worked—yay!

It can actually be proved that this approach correctly identifies biconnected components using the high-level idea of bridges.

It may seem logical, but anything that works without a proof is just magic to me.

I’d love to know if there are other approaches, any cool properties of bridges, and, of course, the proofs related to them.