풀이
M <= N+20이므로, 주어지는 그래프는 최대 20개의 간선만 제거하면 트리가 된다.
즉, 트리와 아주 유사하게 생겼다는 뜻이고, 이는 대부분 노드의 in/out degree가 1이라는 뜻이다.
indegree 또는 outdegree가 2 이상인 노드를 special node로 두자.
special node에서 다른 speical node까지의 경로를 압축하자.
in/out degree가 1인 노드들을 모두 압축해서 하나의 간선으로 치는 것이다.
그러면 노드가 많아야 40개인 그래프가 나온다.
이 그래프에서 TSP를 하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, zip_cnt, zip_num[111111];
int in_deg[111111], out_deg[111111];
vector<int> gp1[111111], path;
struct edg {
int idx; // zipped index
vector<int> path; // [s, e)
};
vector<edg> gp2[111];
void zip(int now, int root, int is_root) {
if (!is_root && zip_num[now]) {
gp2[zip_num[root]].push_back({ zip_num[now],path });
return;
}
path.push_back(now);
for (int nxt : gp1[now]) zip(nxt, root, 0);
path.pop_back();
}
int chk[111];
vector<pair<int, int>> dap;
int feasible(int now, int cnt) {
if (chk[now]) return (cnt == n && now == 1);
chk[now] = 1;
for (int i = 0; i < gp2[now].size(); i++) {
edg nxt = gp2[now][i];
dap.push_back({ now,i });
if (feasible(nxt.idx, cnt+nxt.path.size())) {
return 1;
}
dap.pop_back();
}
chk[now] = 0;
return 0;
}
int main() {
scanf("%d %d", &n, &m);
while (m--) {
int u, v; scanf("%d %d", &u, &v);
gp1[u].push_back(v);
in_deg[v]++;
out_deg[u]++;
}
for (int i = 1; i <= n; i++) {
if (in_deg[i] > 1 || out_deg[i] > 1 || i == 1) {
zip_num[i] = ++zip_cnt;
}
if (in_deg[i] < 1 || out_deg[i] < 1) {
puts("There is no route, Karl!");
return 0;
}
}
for (int i = 1; i <= n; i++)
if (zip_num[i]) zip(i, i, 1);
if (feasible(1, 0)) {
for (auto i : dap) for (auto j : gp2[i.first][i.second].path)
printf("%d ", j);
puts("1");
}
else {
puts("There is no route, Karl!");
}
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이