BOJ 16243 Teoretičar
sorohue가 PS하는 블로그
문제 링크입니다.
문제 요약
50만 개 이하의 간선으로 이루어진 이분 그래프가 주어집니다. 인접한 두 간선의 색이 항상 다르도록 주어진 간선들을 $2^{\lceil \lg \Delta \rceil}$가지 색으로 칠하세요. $\Delta$는 조건을 만족하도록 간선을 색칠하기 위해 필요한 색의 개수의 최솟값입니다.
풀이
일단 $\Delta = \max Deg$입니다. 홀의 결혼 정리에 의해 $k$-regular 그래프는 $k$개의 색으로 칠할 수 있고, 주어진 그래프는 $\max Deg$-regular 그래프의 일부분으로 볼 수 있기 때문입니다.
$2^k$ 꼴로 사용할 수 있는 색의 개수가 나누어떨어짐으로부터 분할 정복이 하고 싶어집니다. 각 정점에 붙어 있는 간선을 두 조로 나누어, 한 조에는 0을, 다른 조에는 1을 할당합니다. 이를 $k$번 반복해 각 간선에 $k$자리 비트열을 할당해 이를 색으로 삼는 방식으로 해를 구성하면 각 정점에 붙어 있는 간선이 서로 다른 색으로 칠해지니 문제를 해결할 수 있습니다. 문제는 어떻게 모든 정점에 대해서 반반이 되도록 간선을 나누냐는 건데…
적당한 간선 사이클을 생각해 봅시다. 사이클의 각 정점에는 들어오는 간선과 같은 개수의 나가는 간선이 붙습니다. 정점들에 붙는 간선들을 반반으로 나눌 수는 있겠네요. 그런데 이렇게 간선을 나눴을 때 이상이 발생하지는 않을까요? 예를 들어서 삼각형 사이클의 경우에는, 두 간선에 0, 1을 할당했을 때 나머지 한 간선에 0/1 중 뭘 할당해도 인접한 간선이랑 색이 겹칠 텐데요.
다행히 문제에서 주어지는 그래프가 이분 그래프기 때문에 그럴 일은 없습니다. 그래서 문제는 이분 그래프에서 오일러 회로를 찾고, 회로를 이루는 간선에 0/1을 번갈아 부여한 뒤에, 같은 비트열은 부여한 간선끼리 모아서 오일러 회로를 또 찾고… 하는 식의 분할 정복으로 해결할 수 있습니다.
근데 오일러 회로가 맨날 찾아지는 건 또 아니잖아요? 단일 연결 요소에 오일러 회로가 존재할 필요충분조건은 모든 정점이 짝수 차수를 가질 것입니다. 우리가 들고 있는 그래프가 꼭 이 조건을 만족하리라는 보장은 없습니다.
하지만 가상의 정점을 이분 그래프의 각 사이드에 하나씩 추가해 반대편 홀수 차수 정점들과 연결해 주고, 가상 정점들이 홀수 차수인 경우 자기들끼리 연결해주면 가상의 정점을 포함해 모든 정점이 짝수 차수를 가지게 됩니다! 이때 원래 있던 각 정점에는, 그 차수가 홀수인 경우에 한해 최대 하나의 간선이 추가되는 것이고 반반으로 나눌 수 있는 한계는 차수가 짝수일 때이므로 가상 정점과 이어지는 간선을 추가한다고 해서 분할 정복을 할 수 없게 되는 일은 일어나지 않습니다.
이상의 내용을 잘 구현하면 ${\cal O}(M \lg M)$에 문제를 해결할 수 있습니다. 제 코드는 약간 비효율적으로 구현되어서 아슬아슬하게 시간 안에 돌아갑니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
vector<pii> e[202020], el[202020], er[202020];
vector<int> nel[202020], ner[202020], dummydummy;
vector<int> ctov[525252], nctov[525252];
int ans[2525252], idx[202020], lastelsz[202020], lastersz[202020], m, L, R, c, bit, cntl, cntr, mx, dummy, dummye;
bool vis[2525252], nc[525252]; int vvis[202020];
void dfs(int now){
while(idx[now] < e[now].size() && ans[e[now][idx[now]].second] == c){
if(vis[e[now][idx[now]].second]){idx[now]++; continue;}
auto [nxt, i] = e[now][idx[now]++]; vis[i] = 1;
dfs(nxt); nc[c] ^= 1;
if(i > m) continue;
if(nc[c]){ans[i] |= bit; er[now].emplace_back(nxt, i); er[nxt].emplace_back(now, i);}
else{el[now].emplace_back(nxt, i); el[nxt].emplace_back(now, i);}
}
if(now >= dummy) return;
}
int main(){
cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
cin >> L >> R >> m; dummy = L+R+1;
for(int i = 1; i <= m; i++){
int u, v; cin >> u >> v; v += L;
e[u].emplace_back(v, i);
e[v].emplace_back(u, i);
}
dummye = m; for(int i = 1; i <= L+R; i++){
mx = max(mx, (int)e[i].size());
if(e[i].size()&1){
dummye++;
e[i].emplace_back(dummy+(i>L), dummye);
e[dummy+(i>L)].emplace_back(i, dummye);
if(i <= L) cntl++;
}
ctov[0].push_back(i);
}
if(cntl&1){
dummye++;
e[dummy].emplace_back(dummy+1, dummye);
e[dummy+1].emplace_back(dummy, dummye);
}
int n = 1; while(n < mx) n <<= 1; cout << n << '\n';
for(bit = 1; bit < n; bit <<= 1){
memset(vis, 0, sizeof(vis)); memset(idx, 0, sizeof(idx)); memset(nc, 0, sizeof(nc)); memset(vvis, -1, sizeof(vvis));
for(c = 0; c < bit; c++){
cntl = cntr = 0;
for(auto i : ctov[c]) dfs(i);
for(auto now : ctov[c]){
if(el[now].size() != lastelsz[now]) nctov[c].push_back(now);
if(er[now].size() != lastersz[now]) nctov[c|bit].push_back(now);
if((el[now].size()-lastelsz[now])&1){nel[now].push_back(c); if(now <= L) cntl++;}
if((er[now].size()-lastersz[now])&1){ner[now].push_back(c|bit); if(now <= L) cntr++;}
lastelsz[now] = el[now].size();
lastersz[now] = er[now].size();
}
if(cntl&1) dummydummy.push_back(c);
if(cntr&1) dummydummy.push_back(c+bit);
ctov[c].clear();
}
for(c = 0; c < 2*bit; c++) swap(ctov[c], nctov[c]);
e[dummy].clear(); e[dummy+1].clear(); dummye = m;
for(int i = 1; i <= L+R; i++){
e[i].clear();
for(int il = 0, nil = 0; il < el[i].size() || nil < nel[i].size();){
if(il == el[i].size()){
dummye++; ans[dummye] = nel[i][nil++];
e[i].emplace_back(dummy+(i>L), dummye);
e[dummy+(i>L)].emplace_back(i, dummye);
}
else if(nil == nel[i].size()) e[i].push_back(el[i][il++]);
else if(ans[el[i][il].second] < nel[i][nil]) e[i].push_back(el[i][il++]);
else{
dummye++; ans[dummye] = nel[i][nil++];
e[i].emplace_back(dummy+(i>L), dummye);
e[dummy+(i>L)].emplace_back(i, dummye);
}
}
for(int ir = 0, nir = 0; ir < er[i].size() || nir < ner[i].size();){
if(ir == er[i].size()){
dummye++; ans[dummye] = ner[i][nir++];
e[i].emplace_back(dummy+(i>L), dummye);
e[dummy+(i>L)].emplace_back(i, dummye);
}
else if(nir == ner[i].size()) e[i].push_back(er[i][ir++]);
else if(ans[er[i][ir].second] < ner[i][nir]) e[i].push_back(er[i][ir++]);
else{
dummye++; ans[dummye] = ner[i][nir++];
e[i].emplace_back(dummy+(i>L), dummye);
e[dummy+(i>L)].emplace_back(i, dummye);
}
}
el[i].clear(); er[i].clear(); nel[i].clear(); ner[i].clear();
lastelsz[i] = lastersz[i] = 0;
}
for(auto& C : dummydummy){
dummye++; e[dummy].emplace_back(dummy+1, dummye); e[dummy+1].emplace_back(dummy, dummye); ans[dummye] = C;
}
sort(e[dummy].begin(), e[dummy].end(), [&](pii& a, pii& b){
return ans[a.second] < ans[b.second];
});
sort(e[dummy+1].begin(), e[dummy+1].end(), [&](pii& a, pii& b){
return ans[a.second] < ans[b.second];
});
dummydummy.clear();
}
for(int i = 1; i <= m; i++) cout << ans[i]+1 << '\n';
}