1. 문제 요약
\(N\)개의 정점과 \(2N-3\)개의 간선이 주어진다. 길이가 같고 길이가 \(3\)이상인 사이클을 \(2\)개 찾아서 출력한다.
2. 풀이
BFS를 통해 트리를 만들어 보자. 그렇다면 \(2N-3\)개의 간선 중, \(N-1\)개는 트리에 포함된 간선이고, 나머지 \(N-2\)개는 포함되지 않는 간선이다. 트리에 포함되지 않는 간선들의 집합을 \(S\)라고 하자.
\(S\)에 속한 간선 \(u, v\)를 생각해보자. 정점 \(u, v\)에 대해 트리 위의 단순 경로를 찾아보자. \(S\)에 포함되지 않는 간선으로 이루어진 \(u\) <-> \(v\)를 잇는 경로가 존재할 것이다. 또한 \(S\)에 속한 간선은 \(u - v\)가 직접적으로 연결되어 있으므로 간선 \(u - v\)를 포함하는 사이클이 된다. LCA를 사용하면 이 과정을 효율적이게 처리할 수 있다.
\(S\)에 속한 간선 \(u, v\)를 포함하는 사이클에 대해 찾아준 뒤 같은 크기의 사이클 두개를 출력해주면 된다. 간선이 \(2N-3\)이라는 조건 때문에 무조건 존재한다.
주의할 점으로 입력으로 주어지는 그래프는 연결 그래프가 아니므로, 각 컴포넌트를 고려해주어야 된다.
3. 증명
왜 같은 크기의 사이클이 두개가 존재하는 지 생각해보자. BFS를 통해 만들어진 트리의 높이를 \(h\)라고 정의하자. 그렇다면 길이가 \(3\) ~ \(2*h\)인 사이클이 존재할 수 있다.
\(S\)에 포함된 간선의 개수는 \(N-2\)개이다. \(N-2\)개의 사이클의 크기가 모두 다르다면 문제에서 원하는 답이 존재하지 않는다.
하지만 간선이 \(2N-3\)개를 BFS로 트리를 만드는 경우 길이가 최대 대략 \(O(logN)\) ~ \(O(\sqrt{N})\)인 사이클만 나올 수 있다. 정확하게 알 수 있는 사실은 \(N-2\)보다 짧은 사이클만 존재하는 것이다. \(N-2\)개의 사이클 중 \(N-2\)보다 작은 길이만 존재하므로 비둘기 집의 원리에 의해 무조건 같은 크기의 사이클이 존재하게 된다.
4. 코드
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
|
#include <bits/stdc++.h>
using namespace std;
const int MAX = 111111;
const int LV = 18;
typedef pair<int, int> pi;
#define u first
#define v second
vector<int> V[MAX], G[MAX];
int dp[LV][MAX], dep[MAX];
bool vit[MAX];
void setTree(int st) {
queue<int> q;
q.push(st); vit[st] = true;
while (q.size()) {
int top = q.front(); q.pop();
for (int w : V[top]) {
if (vit[w]) continue;
G[top].push_back(w);
G[w].push_back(top);
vit[w] = true;
q.push(w);
}
}
}
void dfs(int pos, int p = 0) {
dp[0][pos] = p;
for (int i = 1; i < LV; i++)
dp[i][pos] = dp[i - 1][dp[i - 1][pos]];
for (int w : G[pos]) {
if (w == p) continue;
dep[w] = dep[pos] + 1;
dfs(w, pos);
}
}
int lca(int a, int b) {
if (dep[a] < dep[b]) swap(a, b);
int d = dep[a] - dep[b];
for (int i = 0; d; i++) {
if (d & 1) a = dp[i][a];
d >>= 1;
}
if (a == b) return a;
for (int i = LV - 1; i >= 0; i--)
if (dp[i][a] != dp[i][b]) a = dp[i][a], b = dp[i][b];
return dp[0][a];
}
bool route(int pos, int e, vector<int>& vec, int p = -1) {
if (pos == e) {
vec.push_back(pos);
return true;
}
bool ok = false;
for (int w : G[pos]) {
if (w == p) continue;
if (route(w, e, vec, pos)) ok = true;
}
if (ok) vec.push_back(pos);
return ok;
}
vector<pi> C[MAX];
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n; cin >> n;
vector<pi> vec;
for (int i = 0; i < 2 * n - 3; i++) {
int u, v; cin >> u >> v;
V[u].push_back(v);
V[v].push_back(u);
vec.push_back(pi(u, v));
}
for (int i = 1; i <= n; i++) {
if (vit[i]) continue;
setTree(i); dfs(i);
}
for (auto& p : vec) {
int t = lca(p.u, p.v);
int l = dep[p.u] + dep[p.v] - 2 * dep[t];
if (l >= 2) {
C[l + 1].push_back(p);
}
}
for (int i = 3; i <= n; i++) {
if (C[i].size() < 2) continue;
pi pa = C[i][0], pb = C[i][1];
vector<int> va, vb;
route(pa.u, pa.v, va); route(pb.u, pb.v, vb);
cout << i << "\n";
for (int w : va) cout << w << " ";
cout << "\n";
for (int w : vb) cout << w << " ";
cout << "\n";
return 0;
}
cout << -1;
return 0;
}
|
cs |
'PS > 백준' 카테고리의 다른 글
[백준 5979] 납땜하기 (2) | 2022.09.22 |
---|---|
[백준 25491] Mexor tree (0) | 2022.09.14 |
[백준 25500] 무자비한 최단 경로 (0) | 2022.09.14 |
[백준 15506] 정원사 (0) | 2021.12.21 |
[백준 20052] 괄호 문자열 ? (0) | 2021.12.21 |