https://www.acmicpc.net/problem/19565
# Approach)
$For$ $1 \leq i < j \leq \mid A\mid $, $A_{i} \neq A_{j}$ $\lor A_{i+1} \neq A_{j+1}$ $\iff$ $ \lnot \left(A_{i} = A_{j} \land A_{i+1} = A_{j+1}\right)$ $\iff$ $\lnot \left(\left\{ A_{i}, A_{i+1} \right\} = \left\{ A_{j}, A_{j+1} \right\}\right)$
이로부터 인접한 두 쌍, $A_{i}, A_{i+1}$ 이 모두 다르면 된다.
$1~N$번까지의 정점으로 이루어진 방향 그래프를 생각하자.
모든 쌍 $A_{i}, A_{i+1}$ 에 대해서 정점 $A_{i}$에서 정점$A_{i+1}$로 가는 간선을 대응시켰을때 같은 간선을 두 번 이상 지나지 않으면 된다. 시작점과 끝점을 1로 가지는 회로중 길이가 가장 긴 회로를 찾는 문제로 대응된다.
# Definition)
$E_{i,j}: $ $Edge \ from \ i \ to \ j$
$edges: \left\{ E_{A_{i}, A_{i+1}} \ \mid \ 1 \leq i \leq N-1 \right\}$
$adj: \left\{ edge\_index \ \mid \ edges[edge\_index] = E_{A_{i}, A_{i+1}} \right\}$
임의의 한 정점 $u$ 와 $u$가 아닌 다른 한 정점 $v$에 대해 생각해보자.
길이가 최대로 되며 문제의 조건을 만족하려면 우리가 원하는 회로, $G_{c}$는 다음과 같은 조건을 만족해야 할 것이다.
$E_{u, v}, E_{v, u} \in G_{c}$
따라서 모든 정점에 대해서 양방향으로 모든 간선이 존재하며 $E_{u, u}$도 가능함을 고려한다면
$u$에서 나가는 간선의 수와 들어오는 간선의 수는 항상 같게 된다.
이를 바탕으로 정점 $u$의 차수를 생각해보자.
$deg(u) = deg_{in}(u) + deg_{out}(u) = 2deg_{in}(u)$
모든 정점의 차수는 짝수가 되고 오일러 회로가 존재함을 뜻한다.
Hierholzer’s Algorithm을 이용하여 오일러 회로를 계산해주면 된다.
# Time Complexity)
인접행렬을 이용하는 경우:
$O(\mid V\mid E\mid )$ 이며 $V_{upper\_limit} = 10^3$, $E_{upper\_limit} = 2 \times 10^6$ 의 경우를 가정하면 $O(\mid V\mid E\mid ) \leq 2 \times 10^9$, 시간제한은 1초로 TLE의 가능성이 충분하다.
인접리스트를 이용하는 경우:
$O(\mid E\mid ) \leq$ $E_{upper\_limit} = 2 \times 10^6$
시간제한을 넉넉히 통과한다.
실제로 해당문제는 인접행렬을 이용하며 풀면 TLE를 받게 되니 시간복잡도가 낮은 인접 리스트를 이용하여 구현해야한다는 점에 유의하자.
여담으로 답이 되는 수열의 길이는 cnt로 코드에서 구해도 되지만 모든 가능한 간선이 $n \times n$개라는 것을 생각하면 수열의 길이는 그 보다 1 큰 $n^2 +1$가 됨을 알 수 있다.
#Code(c++)
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
#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define command_param int argc, char *argv[]
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define FOR(i, s, e) for(int i = s; i < e; i++)
#define pf first
#define ps second
#define pii pair<int,int>
#define ll long long
#define lll __int128
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int INF = 987654321;
const ll INFLL = 1e13;
const int mod = 32768;
const int N = 802;
const int st = 50;
int n, m, t, k, start = -1, ans = 0;
vector<vector<int>> adj;
struct Edge{
int u, v;
int cnt;
Edge(int _u, int _v, int _c): u(_u), v(_v), cnt(_c) {};
};
vector<Edge> edges;
void dfs(int cur) {
while(adj[cur].size()) {
int eidx = adj[cur].back();
if(edges[eidx].cnt) {
edges[eidx].cnt--;
dfs(edges[eidx].u + edges[eidx].v - cur);
}
else adj[cur].pop_back();
}
cout << cur << dkdk;
}
void solve() {
adj.resize(n+1);
for1(i, n+1) {
for1(j, n+1) {
if(i == j) {
edges.push_back(Edge(i, i, 1));
int eidx = edges.size() - 1;
adj[i].push_back(eidx);
}
if(i < j) {
edges.push_back(Edge(i, j, 1));
edges.push_back(Edge(j, i, 1));
int eidx = edges.size() - 2;
adj[i].push_back(eidx);
adj[j].push_back(eidx);
eidx++;
adj[i].push_back(eidx);
adj[j].push_back(eidx);
}
}
}
cout << (n*n + 1) << endl;
dfs(1);
}
int main() {
FASTIO;
cin >> n;
solve();
}