BOJ 10806 - 공중도시

문제 링크 : www.acmicpc.net/problem/10806

문제 풀이

step 1

그래프에서 가장 먼저 생각했던 것은 사이클의 관찰이었다. 사이클에서는 어떠한 간선을 한 개 끊어도 임의의 정점에서 다른 정점으로 이동할 수 있다. 또한, 사이클 내의 한 정점이 간선 하나를 끊어도 다른 정점 a에 갈 수 있다면, 사이클 내의 임의의 정점은 간선 하나를 끊어도 정점 a에 갈 수 있다. 이 관찰을 하니까 connecting supertrees라는 문제가 생각났고, 사이클을 하나의 정점으로 치환해야겠다는 생각이 들었다. 

처음 주어진 그래프에서 사이클을 계속해서 정점으로 치환하면 트리가 된다. 그 트리에서 최소환의 간선을 추가해서 사이클을 정점으로 바꾸는 연산을 계속 할 때 결국 한 개의 정점만을 남겨야 된다는 것이다. 

사이클을 만들기 위해서는 리프 두 개를 간선으로 이어야 할 것이다. 따라서 필요한 간선의 개수는 (리프의 수+1)/2 가 될 것이다. 그리고서 간선은 막 이으면 될 줄 알았으나, 틀렸다. 간선을 잘 잇는 것이 문제의 핵심이었다.

step 2

문제가 생기는 경우는 간선을 잇고, 그 간선을 이용하여 사이클을 하나의 정점으로 다시 치환했을 때, 그 정점이 다시 리프가 되어 버리는 경우이다. 

두 정점을 이은 사이클이 다시 리프가 되지 않도록 적당히 두 점을 계속 잡아나가야 한다. 이렇게 점을 잡기 위해서 트리에서 기준 노드를 하나 적당히 잡아서 연결한 모든 쌍이 그 점을 지나가도록 하면 된다. 

step 3

일단 사이클을 하나의 정점으로 치환하는 것은 그래프에서 dfs 트리를 만든 이후에 모든 back edge 에 대해서 back edge가 담당하는 구간을 union 해주면 된다. 그 과정에서 union 을 저장하여 맨처음에 있던 기존의 간선들을 치환한 후, 겹치는 간선을 제거한다. 이때, degree가 1인 정점들의 수를 세준다. 

간선을 잇는 기준은 트리의 리프 센트로이드를 잡으면 된다. 그러면 모든 그룹이 리프개수/2 이하가 되므로, 계속해서 서로 다른 그룹에서 정점을 뽑아낼 수 있다. pq를 사용해 정점이 가장 많이 남은 두 개의 그룹에서 정점을 하나씩 뽑는 것을 반복하여 문제를 해결할 수 있다.

 

굉장히 좋은 문제였다고 생각한다. 전체적인 풀이 과정을 떠올리는데 그렇게 오랜시간이 걸리지는 않았지만, 딱봐도 step 2 부분의 구현이 굉장히 어려울 것 같았다. 그래서 다른 풀이를 생각해보려고 계속 노력했지만, 떠오르지 않아 결국 힘겹게 구현하였다. 하지만, 코딩이 훨씬 더 간단한 step 2의 다른 풀이가 있으니, 잘 생각해서 한 번 찾아보는 것도 좋은 방법이라고 생각한다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef  int ll;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
ll arr[1010101];
ll dep[1010101];
vector<ll> v[1010101];
vector<pii> edg;
ll par[22][201010];
ll p[1010101];
ll cnt;
vector<ll> v2[1010101];
ll vis[1010101];
ll sz[1010101];
vector<ll> as;
vector<ll> gp[1010101];
priority_queue<pii,vector<pii>,less<pii>> pq;
ll gpcnt;
 
bool sf(pii a,pii b){
    return dep[a.ff]>dep[b.ff];
}
 
bool sf2(ll a,ll b){
    return dep[a]>dep[b];
}
 
bool sf3(vector<ll> a, vector<ll> b){
    return a.size()>b.size();
}
 
void gping(ll x){
    vis[x]=1;
    for(auto k:v2[x]){
        if(vis[k]){
            continue;
        }
        gping(k);
    }
    if(v2[x].size()==1) gp[gpcnt].pb(x);
}
 
void dfs(ll x){
    vis[x]=1;
    for(auto k:v[x]){
        if(vis[k]){
            if(k!=par[0][x]) edg.pb({k,x});
            continue;
        }
        dep[k]=dep[x]+1;
        par[0][k]=x;
        dfs(k);
    }
}
void gsz(ll x,ll d){
    for(auto k:v2[x]){
        if(k==d) continue;
        gsz(k,x);
        sz[x]+=sz[k];
    }
    if(v2[x].size()==1) sz[x]++;
}
 
ll cen(ll x,ll d){
    for(auto k:v2[x]){
        if(k==d) continue;
        if(sz[k]>(ll)(as.size())/2) return cen(k,x);  
    }
    return x;
}
 
 
void f(){
    for(ll i=1;i<21;i++)
        for(ll j=1;j<=cnt;j++)
            par[i][j]=par[i-1][par[i-1][j]];
}
 
ll lca(ll a,ll b){
    if(dep[a]>dep[b]) swap(a,b);
    for(ll i=20;i>=0;i--){
        if(dep[par[i][b]]>=dep[a]) b=par[i][b];
    }
    if(a==b) return a;
 
    for(ll i=20;i>=0;i--){
        if(par[i][a]!=par[i][b]){
            a=par[i][a];
            b=par[i][b];
        }
    }
    return par[0][b];
}
 
ll fi(ll x){
    if(p[x]==x) return x;
    return p[x]=fi(p[x]);
}
 
void uf(ll a,ll b){
    a=fi(a);
    b=fi(b);
    if(a==b) return;
    cnt--;
    p[b]=a;
}
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;i++){
        ll a,b;
        scanf("%d %d",&a,&b);
        v[a].pb(b);
        v[b].pb(a);
    }
    cnt=n;
    dep[1]=1;
    dfs(1);
    f();
    for(i=1;i<=n;i++)
        p[i]=i;
    
 
    sort(edg.begin(), edg.end(),sf);
    for(auto k:edg){
        ll a=fi(k.ff);
        ll b=fi(k.ss);
        while(a!=b){
            if(dep[a]>dep[b]) swap(a,b);
            uf(a,b);
            b=par[0][b];
            a=fi(a);
            b=fi(b);
        }
    }
 
 
    for(i=1;i<=n;i++)
        for(auto k:v[i]){
            ll a=fi(i);
            ll b=fi(k);
            if(a==b) continue;
            v2[a].pb(b);
            v2[b].pb(a);
        }
 
    for(i=1;i<=n;i++){
        sort(v2[i].begin(), v2[i].end());
        v2[i].erase(unique(v2[i].begin(), v2[i].end()),v2[i].end());
        if(v2[i].size()==1) as.pb(i);
    }
 
    printf("%d\n",(as.size()+1)/2);
    if(as.size()==2){
        printf("%d %d\n",as[0],as[1]);
        return 0;
    }
 
    for(i=1;i<=n;i++){
        vis[i]=0;
        dep[i]=0;
    }
 
    for(i=1;i<=n;i++){
        if(v2[i].size()){
            gsz(i,-1);
            break;
        }
    }
    ll ce=0;
    
    for(i=1;i<=n;i++){
        if(v2[i].size()){
            ce=cen(i,-1);
            break;
        }
    }
 
    vis[ce]=1;
    for(auto k:v2[ce]){
        gpcnt++;
        gping(k);
    }
    
    sort(gp+1,gp+1+gpcnt,sf3);
 
    if(as.size()%2) gp[gpcnt].pb(gp[gpcnt][gp[gpcnt].size()-1]);
 
    for(i=1;i<=gpcnt;i++)
        pq.push({gp[i].size()-1,i});
 
    for(i=1;i<=(as.size()+1)/2;i++){
        auto a=pq.top();
        pq.pop();
        auto b=pq.top();
        pq.pop();
        printf("%d %d\n",gp[a.ss][a.ff],gp[b.ss][b.ff]);
        pq.push({a.ff-1,a.ss});
        pq.push({b.ff-1,b.ss});
    }
 
}