백준 19565번 - 수열 만들기

On this page

BOJ 19565 - Sequence Construction

Modeling the sequence as a directed graph

We need a sequence whose values are in $1,\dots,N$, whose first and last values are both 1, and in which no ordered adjacent pair appears more than once. An adjacent pair $(x,y)$ is ordered: $(x,y)$ and $(y,x)$ are different, and pairs such as $(x,x)$ are allowed.

Make a directed graph with one vertex for each value. For every ordered pair $(x,y)$, add the directed edge $x\to y$, including a loop from each vertex to itself. A sequence starting and ending at 1 corresponds to a closed walk starting at vertex 1; each consecutive pair in the sequence is exactly one traversed edge. Thus, using each edge at most once gives the required uniqueness condition.

Every vertex has out-degree $N$ and in-degree $N$. The graph is strongly connected because there is a directed edge from every vertex to every vertex. Therefore it has an Euler circuit. Hierholzer’s algorithm finds a circuit that uses every one of its $N^2$ edges exactly once. Starting the algorithm at 1 gives a vertex sequence that starts and ends at 1.

Correctness and maximum length

The Euler circuit traverses each directed edge exactly once, so its consecutive vertex pairs are all distinct and include every possible ordered pair. It contains $N^2$ edges, hence its vertex sequence has $N^2+1$ values.

Conversely, there are only $N^2$ possible ordered pairs over $1,\dots,N$, including the $N$ loops. Any valid sequence can use each pair at most once, so it has at most $N^2$ adjacent pairs and at most $N^2+1$ values. The Euler circuit reaches this bound, so the constructed sequence is maximum length.

We store the outgoing neighbors of each vertex in an adjacency list. Hierholzer’s algorithm removes each edge once and runs in $O(N^2)$ time; the graph and resulting sequence use $O(N^2)$ space.

C++17

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<vector<int>> adj(n + 1);
    for (int from = 1; from <= n; ++from) {
        for (int to = 1; to <= n; ++to) {
            adj[from].push_back(to);
        }
    }

    vector<int> stack = {1};
    vector<int> circuit;
    circuit.reserve(n * n + 1);

    while (!stack.empty()) {
        int cur = stack.back();
        if (!adj[cur].empty()) {
            int next = adj[cur].back();
            adj[cur].pop_back();
            stack.push_back(next);
        } else {
            circuit.push_back(cur);
            stack.pop_back();
        }
    }

    reverse(circuit.begin(), circuit.end());

    cout << circuit.size() << '\n';
    for (int vertex : circuit) {
        cout << vertex << ' ';
    }
    cout << '\n';
    return 0;
}