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

// Process back edges to calculate max distance to LCA for each node
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.

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