[BOJ 22954] 그래프 트리 분할

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

22954번: 그래프 트리 분할

Tag : case work, dsu, constructive

 

문제요약

무향 그래프 \(G(N, M)\)이 주어진다. 간선을 원하는 만큼 삭제해 서로 다른 크기의 트리 2개로 분할하라.

불가능한 경우는 -1을 출력한다.

 

풀이

새벽에 심심해서 tony9402님이 골라온 문제를 풀었다.

일단 일반 그래프인 것이 거슬린다. 트리라면 분할하기 꽤 쉬울텐데...

이는 스패닝 트리를 아무것이나 구해주면 된다.

구한 스패닝 트리에서 조건에 맞는 분할이 불가능하다면 애초에 불가능한 입력이다.

(스패닝 트리는 dsu로 통해 구할 수 있다)

 

그럼 이제 불가능한 경우를 따질 수 있다.

1. 간선을 모두 돌았는데 스패닝 트리를 만들 수 없을 때

    1) 이 때 컴포넌트가 2개일 때

        1) 두 컴포넌트의 크기가 다를 때는 그대로 출력하면 된다. ( O )

        2) 두 컴포넌트의 크기가 같을 때는 불가능하다. ( X )

    2) 컴포넌트가 3개 이상이면 불가능하다. 간선을 추가할 수는 없기 때문 ( X )

2. 스패닝 트리에서 sz[root] != n - sz[i]인 i가 존재하지 않을 때 ( X )

    sz[i]는 i를 루트로 가지는 서브트리의 크기를 의미한다. 

    parent[i] -> i 간선을 끊었을 때 sz[i]는 끊은 간선의 아래쪽 서브트리 크기

    sz[root] - sz[i]는 root와 연결된 쪽의 트리 크기를 의미한다. 

3. n <= 2인 경우 ( X )

    이 경우는 사실 1, 2에서 잘 걸러지지만 문제를 보고 가장 먼저 생각난 케이스라

    if(n<=2) { cout << -1 << endl; return 0; }을 코드에 타이핑해놓고 풀이를 구상했다.

 

이를 잘 구현해주면 맞는다. (나는 1.2.2를 구현에서 놓치고 맞왜틀했었다..)

풀이를 구상하고 코딩하기 전까지 이게 골드 상위까지 되나? 싶었는데 구현량이 생각보다 많다.

구현난이도가 좀 반영된 듯 하다. 

 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'

using namespace std;
using ll = long long;

struct DSU{
    vector<int>pa;int n;
    DSU(int _n):n(_n){pa.resize(n+1);iota(pa.begin(),pa.end(),0);}
    int find(int a){return pa[a]==a?a:(pa[a]=find(pa[a]));}
    void merge(int a,int b){pa[find(b)]=find(a);}
};

int N, M;
vector<pair<int, int>> edge;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> N >> M;
    if(N <= 2) {
        cout << -1 << endl;
        return 0;
    }
    edge.resize(M + 1);
    shared_ptr<DSU> uf = make_shared<DSU>(N);
    vector<int> v;
    for(int i=1; i<=M; i++) {
        cin >> edge[i].first >> edge[i].second;
        if(uf->find(edge[i].first) != uf->find(edge[i].second)) {
            uf->merge(edge[i].first, edge[i].second);
            v.push_back(i);
        }
    }
    auto two = [&]()->void{
        vector<int> a, b;
        a.push_back(1);
        for(int i=2; i<=N; i++)
            if(uf->find(1) == uf->find(i)) a.push_back(i);
            else b.push_back(i);
        if(a.size() == b.size()) {
            cout << -1 << endl;
            exit(0);
        }
        cout << a.size() << ' ' << b.size() << endl;
        for(auto &i : a) cout << i << ' '; cout << endl;
        for(auto &i : v) if(uf->find(1) == uf->find(edge[i].first))
            cout << i << ' '; cout << endl;
        for(auto &i : b) cout << i << ' '; cout << endl;
        for(auto &i : v) if(uf->find(1) != uf->find(edge[i].first))
            cout << i << ' '; cout << endl;
    };
    {
        int cnt = N - (int)v.size();
        if(cnt > 2) {
            cout << -1 << endl;
            return 0;
        }
        if(cnt == 2) {
            two();
            return 0;
        }
    }
    vector<vector<int>>g(N + 1);
    for(auto &k : v) {
        auto [i, j] = edge[k];
        g[i].push_back(j);
        g[j].push_back(i);
    }
    vector<int> chk(N + 1), sz(N + 1), pa(N + 1);
    function<int(int)> dfs = [&](int x)->int{
        chk[x] = 1;
        sz[x] = 1;
        for(auto &i : g[x]) if(!chk[i]) {
            pa[i] = x;
            sz[x] += dfs(i);
        }
        return sz[x];
    };
    dfs(1);
    pair<int, int> e(0, 0);
    for(int i=2; i<=N; i++) {
        if((N%2 or sz[i] != N/2) and sz[i] < N) {
            e = make_pair(i, pa[i]);
            break;
        }
    }
    uf = make_shared<DSU>(N);
    vector<int> t;
    for(auto &i : v){
        auto [p, q] = edge[i];
        if(e == make_pair(p, q) or e == make_pair(q, p)) continue;
        t.push_back(i);
        uf->merge(p, q);
    }
    v.clear(); for(auto &i : t) v.push_back(i);
    two();
}