732F - Tourist Reform - CodeForces Solution

#include "bits/stdc++.h"
#ifdef ON_PC
#include "debug.h"
#else
#define debug(x...)
#define debugV(x...)
#endif
using namespace std;
typedef long long ll;

struct UnionFind {
    int _n;
    vector<int> _par, _cnt;
    // 初始化 [0, n - 1]
    UnionFind() {}
    UnionFind(int n) : _n(n) {
        _par.resize(_n);
        _cnt.resize(_n, 1);
        for (int i = 0; i < _n; i++) _par[i] = i;
    }
    int root(int x) {
        if (_par[x] == x) return x;
        return _par[x] = root(_par[x]);
    }
    inline bool same(int x, int y) { return root(x) == root(y); }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (_cnt[y] < _cnt[x]) std::swap(x, y);
        _par[x] = y;
        _cnt[y] += _cnt[x];
        _cnt[x] = 0;
    }
    inline int cnt(int x) { return _cnt[root(x)]; }
} uf;

template <typename T>
class graph {
   public:
    struct edge {
        int from;
        int to;
        T cost;
    };

    vector<edge> edges;
    vector<vector<int>> g;
    int n;

    graph(int _n) : n(_n) { g.resize(n); }

    virtual int add(int from, int to, T cost) = 0;
};

template <typename T>
class undigraph : public graph<T> {
   public:
    using graph<T>::edges;
    using graph<T>::g;
    using graph<T>::n;
    undigraph(int _n) : graph<T>(_n) {}
    int add(int from, int to, T cost = 1) {
        assert(0 <= from && from < n && 0 <= to && to < n);
        int id = (int)edges.size();
        g[from].push_back(id);
        g[to].push_back(id);
        edges.push_back({from, to, cost});
        return id;
    }
};

template <typename T>
class undigraph_dfs_forest : public undigraph<T> {
   public:
    using undigraph<T>::edges;
    using undigraph<T>::g;
    using undigraph<T>::n;

    vector<int> depth;
    unordered_set<int> bridges;  // edge ids
    vector<int> across_span_edge_cnt;
    // 1:from->to  0:to->from
    // parent->children , children->ancestor
    vector<bool> direction;  // <edge_id, bool>
    vector<bool> vis;        // edge ids

    undigraph_dfs_forest(int _n) : undigraph<T>(_n) {}

    void init() {
        depth = vector<int>(n, -1);
        across_span_edge_cnt = vector<int>(n, 0);
        direction = vector<bool>(edges.size(), 0);
        vis = vector<bool>(edges.size(), 0);
    }

    void clear() {
        depth.clear();
        bridges.clear();
        across_span_edge_cnt.clear();
        direction.clear();
        vis.clear();
    }

   private:
    void do_dfs(int u) {
        for (int id : g[u]) {
            auto& e = edges[id];
            int v = e.from ^ e.to ^ u;
            if (vis[id]) {
                continue;
            }
            vis[id] = 1;
            if (depth[v] != -1) {
                if (depth[v] < depth[u]) {
                    across_span_edge_cnt[u]++;
                    across_span_edge_cnt[v]--;
                    direction[id] = (e.from == u);
                }
                continue;
            }
            direction[id] = (e.from == u);
            depth[v] = depth[u] + 1;
            do_dfs(v);
            across_span_edge_cnt[u] += across_span_edge_cnt[v];
            if (across_span_edge_cnt[v] == 0) {
                bridges.insert(id);
            }
        }
    }

    void do_dfs_from(int v) {
        depth[v] = 0;
        do_dfs(v);
    }

   public:
    void dfs(int v) {
        init();
        do_dfs_from(v);
    }

    void dfs_all() {
        init();
        for (int v = 0; v < n; v++) {
            if (depth[v] == -1) {
                do_dfs_from(v);
            }
        }
    }
};

// assuming this graph don't have self loop, but can have multiple edges

using pa = pair<int, int>;
using ary3 = array<int, 3>;
const int N = 4e5 + 10;

vector<ary3> ans;
vector<int> mg[N];
set<pa> st;

void dfs2(int u, int fa) {
    for (int v : mg[u]) {
        if (v != fa) {
            st.insert(pa(v, u));
            dfs2(v, u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    uf = UnionFind(n + 1);
    auto g = undigraph_dfs_forest<int>(n);
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        u--;
        v--;
        g.add(u, v);
    }
    g.dfs(0);
    for (int id = 0; id < g.edges.size(); id++) {
        int u = g.edges[id].from, v = g.edges[id].to;
        if (!g.direction[id]) {
            swap(u, v);
        }
        ans.push_back(ary3{u, v, id});
        if (!g.bridges.count(id)) {
            uf.unite(u, v);
        }
    }
    for (int id : g.bridges) {
        int u = g.edges[id].from, v = g.edges[id].to;
        int pu = uf.root(u), pv = uf.root(v);
        mg[pu].push_back(pv);
        mg[pv].push_back(pu);
    }
    int st_vtx = -1;
    for (int i = 0; i < n; i++) {
        if (uf.cnt(i) > 0 and (st_vtx == -1 || uf.cnt(i) > uf.cnt(st_vtx))) {
            st_vtx = uf.root(i);
        }
    }
    dfs2(st_vtx, st_vtx);
    int max_val = 0;
    if (st.size()) {
        max_val = uf.cnt(st_vtx);
    } else {
        max_val = n;
    }
    debugV(st, st_vtx);
    sort(ans.begin(), ans.end(), [&](auto l, auto r) { return l[2] < r[2]; });
    cout << max_val << '\n';
    for (auto& a : ans) {
        if (st.count(pa(uf.root(a[1]), uf.root(a[0])))) {
            swap(a[0], a[1]);
        }
        cout << a[0] + 1 << " " << a[1] + 1 << '\n';
    }
    return 0;
}