[BOJ 16583] Boomerangs

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

16583번: Boomerangs

Tag : constructive, greedy

 

문제요약

양방향 그래프 G(v, e)를 인접한 2개의 간선들로 분할하라.

이 때 인접한 2개의 간선쌍의 개수를 최대화해야한다. 

 

풀이

이 문제를 일반 그래프에서 푸는 것은 굉장히 어려울 것 같습니다. 

그러니 일단은 G가 트리라 가정하고 풀어보겠습니다. 

 

트리에서는 항상 \( [\frac{n-1}{2}] \)개만큼의 부메랑을 만들 수 있습니다.

 

정점이 1개인 트리는 0개의 부메랑을 만들 수 있고

정점이 n + 2개인 트리는 정점이 n개인 트리의 적절한 위치에 부메랑을 달아서 만들 수 있습니다.

따라서 홀수에서는 항상 \( \frac{n - 1}{2} \)개의 부메랑을 만들 수 있고

짝수에서는 \( \frac{n-2}{2}  \)개를 만들 수 있습니다. 

 

트리에서는 다음과 같은 방법으로 문제를 해결할 수 있습니다. 

1. 리프의 부모 x에 대해서 자식의 수가 짝수라면 자식 두개 + 자신을 연결해 부메랑을 만들고 자식들을 지운다. 

2. 홀수라면 \([\frac{m}{2}]\)개만큼의 부메랑을 [1]의 방법으로 잇고 남은 하나는 부모 + 자신 + 남은 하나로 이은 다음 자식들과 자신을 지운다.

3. [1], [2]를 남은 간선이 1개 이하일 때까지 반복

 

void dfs(int x, int p) {
    for(auto &i : graph[x]) dfs(i, x);
    vector<int> child;
    for(auto &i : graph[x]) if(chk[i] == 0) child.push_back(i);
    for(int i=0; i+1<child.size(); i+=2) {
        int l = child[i], r = child[i + 1];
        ans.push_back({l, x, r});
    }
    if(child.size() % 2 and p > 0) {
        chk[x] = 1;
        ans.push_back({p, x, child.back()});
    }
}

---

트리에서 푸는 방법은 알아냈으니 일반 그래프를 트리로 바꿀 수 있으면 풀 수 있을 것 같습니다. 

문제에 필요한 정보는 건들지 않고 트리로 바꿔야하는데 생각보다 간단합니다.

dfs를 해보면서 백엣지가 생기는 부분에서 정점을 하나 새로 만들어 사이클을 막아주면 됩니다.

당연히 새로 만든 정점의 원본 정점이 어떤 것인지는 기억해야합니다. 

 

 

void maketree(int x, int p) {
    visited[x] = 1;
    for(auto &i : v[x]) if(mp[{x, i}] == 0) {
        mp[{x, i}] = 1;
        mp[{i, x}] = 1;
        if(visited[i]) {
            re[++center] = i;
            graph[x].push_back(center);
        } else {
            graph[x].push_back(i);
            maketree(i, x);
        }
    }
}

---

이제 일반 그래프에서 문제를 풀 수 있습니다. 

입력이 연결 그래프가 아닐 수 있다는 점에 주의해야합니다. 

 

트리로 변한하는 아이디어가 미친 것 같습니다.... 

힌트를 안받았으면 절대 못풀었을 문제네요.

 

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

using namespace std;
using ll = long long;

int n, m, center;
int chk[202020];
int re[202020];
int visited[202020];
map<pair<int, int>, int> mp;
vector<tuple<int, int, int>> ans;
vector<int> v[101010];
vector<int> graph[202020];

void maketree(int x, int p) {
    visited[x] = 1;
    for(auto &i : v[x]) if(mp[{x, i}] == 0) {
        mp[{x, i}] = 1;
        mp[{i, x}] = 1;
        if(visited[i]) {
            re[++center] = i;
            graph[x].push_back(center);
        } else {
            graph[x].push_back(i);
            maketree(i, x);
        }
    }
}

void dfs(int x, int p) {
    for(auto &i : graph[x]) dfs(i, x);
    vector<int> child;
    for(auto &i : graph[x]) if(chk[i] == 0) child.push_back(i);
    for(int i=0; i+1<child.size(); i+=2) {
        int l = child[i], r = child[i + 1];
        ans.push_back({re[l], re[x], re[r]});
    }
    if(child.size() % 2 and p > 0) {
        chk[x] = 1;
        ans.push_back({re[p], re[x], re[child.back()]});
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
//    freopen("input.txt", "r", stdin);
    
    cin >> n >> m; center = n;
    for(int i=1; i<=m; i++) {
        int p, q; cin >> p >> q;
        v[p].push_back(q);
        v[q].push_back(p);
    }
    for(int i=1; i<=n; i++) re[i] = i;
    for(int i=1; i<=n; i++) if(visited[i] == 0) {
        maketree(i, 0);
        dfs(i, 0);
    }
    cout << ans.size() << endl;
    for(auto &[i, j, k] : ans) cout << i << ' ' << j << ' ' << k << endl;
}