취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 24504번 문제인 blobcry이다.
문제는 아래 링크를 확인하자.

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

먼저 매 순간 두 개의 다리가 지워지므로 다리의 개수 $M$이 짝수이면 어떤 다리도 마지막 남은 하나의 다리가 될 수 없다. 다음 문단부터는 $M$이 홀수라 가정하자.

어떤 다리가 마지막으로 남을 수 있다는 것과 해당 다리를 제외한 다리들로 구성된 그래프는 주어진 조건을 따라 다리를 모두 없앨 수 있다는 것은 동치임을 관찰하자. 이 때, 다음이 성립함을 관찰하면 이 문제를 푸는 것은 "없앴을 때 그래프를 다리의 개수가 각각 홀수인 두 connected component로 나눠버리는 다리"를 찾는 것과 같음을 쉽게 확인할 수 있다.

짝수 개의 다리를 갖는 connected component는 주어진 조건을 따라 모든 다리를 항상 없앨 수 있다.

위 관찰은 다음과 같은 두 명제를 보이는 것으로 귀납적으로 증명할 수 있다. 그 증명은 어렵지 않으므로 간단한 스케치만 남겨 둔다.

(1) 주어진 connected component가 홀수 개의 에지로 이루어져 있다면 임의의 섬에서 하나의 에지를 지워 짝수 개의 에지로 이루어진 connected component(여러 개일 수 있음)를 얻을 수 있다.

(1)의 추가 설명: 고른 섬이 둘 이상의 섬으로 이루어진 biconnected component에 포함된다면 이면 해당 component에 포함되는 에지를 하나 지우면 되고, 그렇지 않다면 전체 에지가 홀수 개임을 이용해 끊었을 때 두 connected component의 각 에지의 개수가 모두 짝수가 되게 하는 에지가 항상 존재하게 됨을 보이자.

(2) 주어진 connected component가 짝수 개의 에지로 이루어져 있다면 임의의 섬에서 하나의 에지를 지워 홀수 개의 에지로 이루어진 connected component(와 덤으로 나올 수 있는 짝수 개의 에지로 이루어진 connected component)를 얻을 수 있다.

따라서 마지막으로 남을 수 있는 다리는 주어진 그래프에서 "끊었을 때 크기가 홀수인 두 component로 그래프를 쪼개는 다리"를 제외한 모든 다리들이다. 주어진 그래프의 bridge들을 한 번씩 확인해 문제를 해결하자. 해당 bridge를 끊었을 때 나누어지는 두 component가 각각 포함하는 에지의 수는 Block-cut Tree(각 biconnected component를 노드로 갖는 Tree) 위에서의 Tree DP와 같은 접근으로 빠르게 계산할 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int N, M;
map<pair<int, int>, int> mp;
vector<int> G[300001];
bool ans[300001];
int dfidx, dfi[300001];

pair<int, int> dfs(int cur, int par) { // 리턴값: 만난 최소 dfi, 에지 수
    dfidx++;
    int ret = dfi[cur] = dfidx, cnt = 0;
    if (cur == par) cnt++;
    
    for (auto &nxt:G[cur]) {
        if (nxt == par) continue;
        if (dfi[nxt]) ret = min(ret, dfi[nxt]);
        else {
            auto tmp = dfs(nxt, cur);
            ret = min(ret, tmp.first);
            cnt += tmp.second;
        }
    }
    
    cnt += G[cur].size() - 1;
    if (ret == dfi[cur] && ((cnt / 2) & 1) && par) {
        ans[mp[make_pair(min(cur, par), max(cur, par))]] = 1;
    }
    cnt++;
    return make_pair(ret, cnt);
}

int anscnt;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    if (M % 2 == 0) {
        cout << 0;
        return 0;
    }
    for (int i = 1; i <= M; i++) {
        int x, y; cin >> x >> y;
        G[x].emplace_back(y);
        G[y].emplace_back(x);
        mp.insert(make_pair(make_pair(min(x, y), max(x, y)), i));
    }
    
    dfs(1, 0);
    
    for (int i = 1; i <= M; i++) {
        if (ans[i]) continue;
        anscnt++;
    }
    
    cout << anscnt << '\n';
    for (int i = 1; i <= M; i++) {
        if (ans[i]) continue;
        cout << i << ' ';
    }
}