BOJ 10806 공중도시

사용한 알고리즘

BCC, Union-find

알고리즘 설명

먼저 다리가 끈어지면 분리되는 점, 곧 단절선을 찾아야 한다.
단절선을 찾기위해서 BCC(Biconnected Component) 알고리즘을 적용한다.
여기서 같은 BCC로 묶이는 Vertex들을 Union-find로 합쳐준다.
이후 남은 단절선으로만 구성된 그래프를 바라보자.
단절선 중, SingleNode, Node가 하나만 연결된 Vertex들을 서로서로 연결 시켜 주면 모든 단절선을 없앨 수 있음을 알 수 있다.
SingleNode가 짝수인 경우, 모두 서로 연결이 가능하다. 고로 답은 SingleNode/2 개
여기서, SingleNode 개수가 홀수인 경우, 남은 SingleNode와 아무 Vertex와 연결시키면 된다. 고로 답은 SingleNode/2+1 개

풀이

// baekjoon 10806 yechan
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX_N=100001;

int N, M, C1, C2, root[MAX_N], disc[MAX_N];
vector<int> adj[MAX_N];
vector<pair<int, int> > connect;
vector<int> node[MAX_N];

int find(int x) {
    if (!root[x]) return x;
    return root[x]=find(root[x]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (a > b) swap(a,b);
    root[b]=a;
}

void dfs(int here, int parent, int distance) {
    disc[here] = distance;
    int parent_conut=0;
    for (int i=0; i<adj[here].size(); i++) {
        int there = adj[here][i];
        if (there == here) continue;
        if (there == parent && !parent_conut) {
            parent_conut++;
            continue;
        }
        if (!disc[there]) {
            dfs(there, here, distance+1);
            if (disc[there] == distance+1) connect.push_back({here, there});
            else merge(here, there);
        }
        disc[here] = min(disc[here], disc[there]);
    }
}

int main() {
    scanf("%d%d", &N, &M);
    for (int i=0; i<M; i++) {
        scanf("%d%d", &C1, &C2);
        adj[C1].push_back(C2);
        adj[C2].push_back(C1);
    }
    dfs(1, -1, 1);
    for (int i=0; i<connect.size(); i++) {
        int a = find(connect[i].first);
        int b = find(connect[i].second);
        node[a].push_back(b);
        node[b].push_back(a);
    }
    int singleNodeCnt = 0;
    vector<int> v;
    for (int i=1; i<=N; i++){
        if (node[i].size() == 1) {
            singleNodeCnt++;
            v.push_back(i);
        }
    }
    printf("%d\n", (singleNodeCnt+1)/2);

    for (int i=1; i<v.size(); i+=2)
        printf("%d %d\n", v[i-1], v[i]);

    if (v.size() % 2)
        printf("%d %d\n", v[v.size()-2], v[v.size()-1]);
    return 0;
}