백준 33722 [B] 이진 매칭

https://www.acmicpc.net/problem/33722
 
문제 요약) 무방향 그래프에서 모든 정점의 차수가 홀수이도록 간선 적절히 지우기
 
가능/불가능 따지기 + 가능하다면 해 구성하기 형식의 문제는 가능한 필요충분조건을 찾으면 해를 구성하는 방식도 따라오는 경우가 많다. 서로 다른 컴포넌트에 속한 정점끼리는 서로 영향을 주지 못하니, 연결 그래프에서 문제를 푼다고 생각하자.
 
초기 그래프에서 차수가 홀수인 정점을 홀수 정점, 짝수인 정점을 짝수 정점이라 하자. 목표는 간선을 적절히 선택하여 짝수 정점을 모두 없애는 것이다. 어떤 간선의 선택 여부를 바꾸면 해당 간선 양 끝 정점의 차수의 홀짝성이 뒤집힌다는 사실을 바탕으로 케이스를 나눠 보자.

• 두 짝수 정점이 인접해 있다면 두 정점 모두 홀수 정점으로 바꿀 수 있다.
• 홀수 정점과 짝수 정점이 인접해 있다면 홀수 정점과 짝수 정점의 위치를 바꿀 수 있다.

인접한 홀수 정점과 짝수 정점의 위치를 바꾸는 것을 짝수 정점을 한 칸 이동시킨다고 생각해 보면, 두 짝수 정점이 멀리 떨어져 있더라도 짝수 정점을 한 칸씩 옮겨 인접하게 만든 뒤 없앨 수 있다. 이는 두 짝수 정점을 잇는 어떤 단순 경로를 찾은 뒤 해당 경로상의 모든 간선의 선택 여부를 뒤집는 것과 같다. 따라서, 짝수 정점의 개수가 짝수라면 짝수 정점을 아무렇게나 둘씩 짝 지은 뒤 위 과정을 수행하여 모든 짝수 정점을 없앨 수 있다.
 
어떤 경우에도 홀수 정점, 짝수 정점 각각의 개수의 홀짝성은 바뀌지 않으니, 짝수 정점의 개수가 홀수라면 모든 짝수 정점을 없애는것은 불가능하다. 따라서 짝수 정점끼리 짝 지은 뒤 경로상의 간선 사용 여부를 뒤집는 작업을 빠르게 할 수 있다면 문제를 풀 수 있다.
 
짝수 정점의 개수가 짝수이고, 그래프가 트리라고 가정해 보자. 임의의 정점 X를 잡았을 때, X의 서브트리에 짝수 정점이 홀수 개 있다면 서브트리에 짝 없는 정점이 하나 남을 테니 X와 부모를 잇는 간선을 뒤집어야 한다. 반대로, X의 서브트리에 짝수 정점이 짝수 개 있다면 서브트리 안에서 모두 짝 지어지고 서브트리 바깥의 짝수 정점과 매칭될 정점이 없으니 X와 부모를 잇는 간선을 그대로 두어야 한다. 실제 정점 쌍을 모두 구할 필요는 없고 경로상의 간선만 뒤집으면 되니, 트리에서 dfs를 수행하며 이러한 과정을 거치면 짝 지어지는 두 정점은 부모 간선을 뒤집으며 올라가다 LCA에서 만나게 되며, 모든 짝수 정점 쌍 사이의 간선이 뒤집히게 된다.
 
그래프에서도 dfs 트리에 속한 간선만 고려하고 back edge는 그대로 두면 사실상 트리에서 문제를 해결하는 것과 같으니 문제를 풀 수 있다.
 
꽤 어려운데 왜 P4인지 모르겟다. 감이죽은건가..

 

#include <bits/stdc++.h>
using namespace std;
 
vector<pair<int,int>> G[1010101];
int use[1010101], chk[1010101];
 
int dfs(int v){
    chk[v] = 1;
    int ret = G[v].size() & 1 ^ 1;
    for (auto [i,id] : G[v]){
        if (chk[i]) continue;
        int res = dfs(i);
        ret ^= res;
        use[id] ^= res;
    }
    return ret;
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    int N, M;
    cin >> N >> M;
    for (int i = 1; i <= M; i++){
        int a, b;
        cin >> a >> b;
        G[a].emplace_back(b, i);
        G[b].emplace_back(a, i);
        use[i] = 1;
    }
    for (int i = 1; i <= N; i++){
        if (!chk[i] and dfs(i)){
            cout << -1;
            return 0;
        }
    }
    vector<int> ans;
    for (int i = 1; i <= M; i++) {
        if (use[i])
            ans.push_back(i);
    }
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (int i : ans) cout << i << ' ';
}