lessons/参考实现/02-强连通与双连通/CodeForces-732F.cpp

#include <algorithm>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>
using namespace std;
struct E { int to, id; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<pair<int, int>> edge(m), answer(m, {-1, -1});
    vector<vector<E>> g(n);
    for (int id = 0; id < m; ++id) {
        int u, v; cin >> u >> v; --u; --v; edge[id] = {u, v};
        g[u].push_back({v, id}); g[v].push_back({u, id});
    }

    vector<int> dfn(n), low(n), par(n, -1), pe(n, -1);
    vector<size_t> it(n); vector<bool> bridge(m); int timer = 0;
    vector<int> st{0}; dfn[0] = low[0] = ++timer;
    while (!st.empty()) {
        int u = st.back();
        if (it[u] < g[u].size()) {
            E e = g[u][it[u]++];
            if (e.id == pe[u]) continue;
            if (!dfn[e.to]) {
                par[e.to] = u; pe[e.to] = e.id;
                dfn[e.to] = low[e.to] = ++timer; st.push_back(e.to);
            } else low[u] = min(low[u], dfn[e.to]);
        } else {
            st.pop_back();
            if (par[u] != -1) {
                if (low[u] > dfn[par[u]]) bridge[pe[u]] = true;
                low[par[u]] = min(low[par[u]], low[u]);
            }
        }
    }

    vector<int> comp(n, -1), comp_size; int count = 0;
    for (int s = 0; s < n; ++s) if (comp[s] == -1) {
        int size = 0; vector<int> work{s}; comp[s] = count;
        while (!work.empty()) {
            int u = work.back(); work.pop_back(); ++size;
            for (E e : g[u]) if (!bridge[e.id] && comp[e.to] == -1) {
                comp[e.to] = count; work.push_back(e.to);
            }
        }
        comp_size.push_back(size); ++count;
    }
    int root = int(max_element(comp_size.begin(), comp_size.end()) - comp_size.begin());

    // 非桥边：在各边双分量中做 DFS，树边向下、返祖边向上。
    vector<bool> seen_vertex(n), used_edge(m);
    vector<size_t> orient_it(n);
    for (int s = 0; s < n; ++s) if (!seen_vertex[s]) {
        vector<int> dfs{s}; seen_vertex[s] = true;
        while (!dfs.empty()) {
            int u = dfs.back();
            while (orient_it[u] < g[u].size() &&
                   (bridge[g[u][orient_it[u]].id] || used_edge[g[u][orient_it[u]].id])) {
                ++orient_it[u];
            }
            if (orient_it[u] == g[u].size()) { dfs.pop_back(); continue; }
            E e = g[u][orient_it[u]++];
            used_edge[e.id] = true; answer[e.id] = {u, e.to};
            if (!seen_vertex[e.to]) { seen_vertex[e.to] = true; dfs.push_back(e.to); }
        }
    }

    vector<vector<pair<int, int>>> tree(count);
    for (int id = 0; id < m; ++id) if (bridge[id]) {
        auto [u, v] = edge[id];
        tree[comp[u]].push_back({comp[v], id});
        tree[comp[v]].push_back({comp[u], id});
    }
    vector<int> parent(count, -1); queue<int> q; parent[root] = root; q.push(root);
    while (!q.empty()) {
        int c = q.front(); q.pop();
        for (auto [to, id] : tree[c]) if (parent[to] == -1) {
            parent[to] = c; q.push(to);
            auto [u, v] = edge[id];
            // 子分量 -> 父分量
            answer[id] = (comp[u] == to) ? pair<int, int>{u, v}
                                         : pair<int, int>{v, u};
        }
    }
    cout << comp_size[root] << '\n';
    for (auto [u, v] : answer) cout << u + 1 << ' ' << v + 1 << '\n';
}