把编号看成弧、把弧的起点终点看成新图的顶点,座位圈等价于该图的欧拉回路,用 Hierholzer 迭代求出一条弧序列。
OJ: roj
题目 ID: 1738
难度:提高+/省选-
标签:图论欧拉回路构造python
创建: 2026-10-08 10:20
更新: 2026-10-08 10:20
形式化题目
有
四个候选值看起来是两对,其实在模
输入是多组数据,每行一个整数
以样例 0 1 2 5 3 7 6 4。逐对检查:
正解
思路
朴素做法。 把
关键转化:把数字从"点"改成"边"。 重新造一张只有
为什么这两个问题是等价的? 看两条相邻的座位号
最后一步用的是
中一条弧序列,其标号序列就是一圈合法的座位; - 反过来,一圈合法座位也唯一对应
中一条弧序列。
也就是说,原问题的哈密顿回路
欧拉回路一定存在。 顶点
Hierholzer 求欧拉回路。 从顶点 used[v] 记下已经
用掉几条出弧,取 path 并回退一步。因为记录发生在回溯(后序)阶段,
path 里是逆访问序,倒过来输出就是欧拉回路的弧标号序列。
以 path
代码
Python 版:
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-08 10:20
# update_at: 2026-10-08 10:20
import sys
START = -1 # 栈底哨兵:起点顶点没有「进入它的弧」,回溯时跳过
def euler_cycle(n: int) -> list[int]:
"""返回顶点集 Z_n 上一条欧拉回路的弧标号序列,即一组合法座位圈。
弧 a 从顶点 a//2 出发指向顶点 a%n,共 2n 条;每个顶点出入度都是 2,
故必存在欧拉回路。Hierholzer 迭代写法:能走就走,走不动了把「进来的那条弧」
压进 path,最后把 path 逆序即为答案。
"""
used = bytearray(n) # 顶点 v 已用掉的出弧数(0 或 1 或 2)
stack = [START] # 栈元素是「进入当前顶点的弧号」
path: list[int] = [] # 回溯顺序登记的弧号(答案的逆序)
while stack:
arc = stack[-1]
v = 0 if arc == START else arc % n # 弧 arc 的头顶点
if used[v] < 2: # 还有没走过的出弧,继续深入
used[v] += 1
stack.append(2 * v + used[v] - 1) # 出弧编号:2v 或 2v+1
else: # 出弧走完,回溯时登记进来的弧
path.append(arc)
stack.pop()
return path[-2::-1] # 逆序,并丢掉末尾的起点哨兵
def solve() -> None:
data = map(int, sys.stdin.buffer.read().split())
print('\n'.join(' '.join(map(str, euler_cycle(n))) for n in data))
if __name__ == "__main__":
solve()C++ 版(同一算法):
// Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
// rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
// rainboy的学习导航网站: https://idx.roj.ac.cn
// create_at: 2026-10-08 10:20
// update_at: 2026-10-08 10:20
//
// ROJ 1738《圆桌聚会》
// 座位圈 x_0..x_{2n-1} 需满足 x_{i+1} ≡ 2*x_i + k (mod 2n),k∈{0,1}。
// 把数字 0..2n-1 看成边:弧 a_y 从顶点 y/2 指向顶点 y mod n(顶点集 Z_n)。
// 每个顶点出度=入度=2,故存在欧拉回路;弧标号序列即合法座位圈。
// Hierholzer 迭代实现(显式栈,防爆系统栈),每条边只走一次,O(n)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static const int MAXN = 500000; // n 的上界
static char used[MAXN]; // 顶点 v 已经走过的出弧数(0..2)
static int stk[2 * MAXN + 5]; // 显式栈:栈元素是「进入当前顶点的弧号」,起点为 -1
static int path[2 * MAXN + 5]; // 回溯时记录的弧号,逆访问序
static char outbuf[1 << 23]; // 输出缓冲
static int outpos = 0;
/** 把非负整数写进输出缓冲,缓冲将满时先落盘。 */
inline void writeInt(int x) {
if (outpos > (1 << 23) - 32) { fwrite(outbuf, 1, outpos, stdout); outpos = 0; }
char tmp[12];
int len = 0;
if (x == 0) tmp[len++] = '0';
while (x > 0) { tmp[len++] = char('0' + x % 10); x /= 10; }
while (len--) outbuf[outpos++] = tmp[len];
}
int main() {
// 输入只有若干行整数,整块读入后自己扫数字,比 cin/scanf 逐个解析快得多
string inbuf;
{
char chunk[1 << 16];
size_t got;
while ((got = fread(chunk, 1, sizeof(chunk), stdin)) > 0) inbuf.append(chunk, got);
}
inbuf.push_back('\0');
char *p = &inbuf[0];
while (true) {
while (*p && (*p < '0' || *p > '9')) ++p; // 跳过空白等分隔符
if (*p == '\0') break;
int n = 0;
while (*p >= '0' && *p <= '9') n = n * 10 + (*p++ - '0');
if (n <= 0) continue;
for (int i = 0; i < n; i++) used[i] = 0; // 只清 0..n-1,避免 O(T*MAXN)
int top = 0, cnt = 0;
stk[top++] = -1; // 起点 0 没有「进入它的弧」
while (top > 0) {
int a = stk[top - 1]; // 当前所在的弧
int v = (a < 0) ? 0 : a % n; // 弧 a 的头 = a mod n
if (used[v] < 2) { // 还有没走过的出弧,就继续深入
int y = 2 * v + used[v]++;
stk[top++] = y;
} else { // 出弧走完,回溯时登记进来的那条弧
path[cnt++] = a;
--top;
}
}
// path 是逆访问序,最后一项是起点哨兵 -1;倒着输出即为欧拉回路的弧序列
for (int i = cnt - 2; i >= 0; --i) {
if (i != cnt - 2) outbuf[outpos++] = ' ';
writeInt(path[i]);
}
outbuf[outpos++] = '\n';
}
if (outpos) fwrite(outbuf, 1, outpos, stdout);
return 0;
}复杂度
- 时间:
有 个顶点、 条弧,Hierholzer 每条弧恰好被压栈、出栈一次, 所以单组数据是严格的 ,多组数据总和 。每组只清 used[0..n-1], 不能memset整块数组,否则会退化成。 实测 10 个数据点(最大单点 )在限时 2000 ms 内余量很大。 - 空间:
used是字节,显式栈与答案数组各 个 int,共。 时约 8 MB,远低于 256 MB。 - 实现要点:DFS 深度最坏可达
,递归写法会爆系统栈,必须用数组模拟显式栈; 输出最多有 个整数(数十 MB),要手写缓冲输出而不是逐个 cout。
总结
- 换一个"点/边"的视角,NP 难题变成线性算法:把
从顶点降级成弧之后, “相邻约束"就变成了"弧头接弧尾”,哈密顿回路自动变成欧拉回路。这类 "在线图上求哈密顿回路 在原图上求欧拉回路"的对偶是构造题的常见套路, 识别信号是约束形如 这种"左移一位再加一位"的递推。 - 存在性可以先证再写:入度
出度 强连通 欧拉回路存在, 所以程序里不需要任何回溯或判无解,直接一路走到底。 - Hierholzer 的记录时机是后序:栈里存"进入当前顶点的那条弧",出弧用尽才登记, 最后整体逆序,这样天然避免了显式的路径拼接与插入。
- 工程细节决定能不能过:显式栈防爆栈、按需清空防超时、缓冲输出防 I/O 瓶颈。
数据来源说明:素材源目录带有数据生成脚本
data.py,data/下的 10 个测试点是 按题面数据范围自行分层生成的(、 、 、 、随机小/中/大规模、 顶格与多测负载),并非官方原始数据;题面本身是从网络材料重建的, 与官方原题的评测数据可能存在偏差。本文所述算法对 的全部 都给出合法构造,因此结论不受影响。