10806번: 공중도시

https://www.acmicpc.net/problem/10806


더럽게 코딩했으니 나중에 다시 풀어야겠다.

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5;
int n, m, t[MAX_N + 1], flag[MAX_N + 1];
vector<int> adj[MAX_N + 1], nadj[MAX_N + 1];
vector<pair<int, int> > r;
int f(int x) {
    if (x == flag[x]) return x;
    return flag[x] = f(flag[x]);
}
void dfs(int h, int p, int d) {
    t[h] = d;
    int cnt = 0;
    for (auto it : adj[h]) {
        if (it == h || it == p && !cnt++) continue;
        if (!t[it]) {
            dfs(it, h, d + 1);
            if (t[it] == d + 1) r.push_back({ h,it });
            else {
                int ra = f(h), rb = f(it);
                if (ra > rb) swap(ra, rb);
                flag[rb] = ra;
            }
        }
        t[h] = min(t[h], t[it]);
    }
}
pair<int, int> dfs2(int h, int p) {
    vector<pair<int, int> > v2;
    vector<int> v1;
    for (auto it : nadj[h]) {
        if (it == p) continue;
        pair<int, int> p = dfs2(it, h);
        if (!p.second) v1.push_back(p.first);
        else v2.push_back(p);
    }
    if (v1.size() + v2.size() == 0) return{ h,0 };
    for (int i = 1; i < v2.size(); i += 2) {
        printf("%d %d\n", v2[i - 1].first, v2[i].first);
        v1.push_back(v2[i - 1].second);
        v1.push_back(v2[i].second);
    }
    if (v1.empty()) return v2.back();
    if (v2.size() % 2) {
        printf("%d %d\n", v2.back().first, v1.back());
        v1.back() = v2.back().second;
    }
    for (int i = 1; i < v1.size() - 1; i += 2) printf("%d %d\n", v1[i - 1], v1[i]);
    if (v1.size() % 2) return{ v1.back(),0 };
    return{ v1[v1.size() - 2],v1.back() };
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d %d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) flag[i] = i;
    dfs(1, -1, 1);
    for (auto it : r) {
        int ra = f(it.first), rb = f(it.second);
        nadj[ra].push_back(rb);
        nadj[rb].push_back(ra);
    }
    int rcnt = 0;
    for (int i = 1; i <= n; i++) rcnt += nadj[i].size() == 1;
    printf("%d\n", (rcnt + 1) / 2);
    pair<int, int> p = dfs2(1, -1);
    if (nadj[1].size() == 1) {
        if (p.first && p.second) printf("%d %d\n%d %d", 1, p.first, 1, p.second);
        else if (p.first) printf("%d %d", 1, p.first);
    }
    else if (nadj[1].size() >= 2) {
        if (p.first && p.second) printf("%d %d", p.first, p.second);
        else printf("%d %d", 1, p.first);
    }
    return 0;
}