片段逼出「每条弧的唯一后继」,粘合成链后收缩成超边,再在收缩图上判从路口 1 出发的欧拉回路:逐点入度等于出度且带边的点弱连通。
OJ: roj
题目 ID: 1737
难度:提高+/省选-
标签:图论欧拉回路python
创建: 2026-10-07 20:32
更新: 2026-10-07 20:32
形式化题目
给定有向图
求是否存在一条从路口
形式化地:路线是全体
并定义环状后继
注意
正解
思路
片段其实是在点名规定后继。 一条闭合路线
怎么记录这个指定。 对每条边 nxt[e]、prv[e]:片段要求 nxt[e] = f、prv[f] = e。因为 nxt、prv 各自至多有一个值,任何人来改写都要先比对,
不一致立刻判 NIE。同一片段内若同一条边出现两次,也直接 NIE(边只能走一次)。
被指定的边必然分解成「链」和「环」。 nxt 是部分函数,沿 nxt 走只有两种归宿:
走到一条没有后继的边(链),或者绕回自己(环,即闭合轨道)。这两种形状的可行性完全不同:
- 链:整条链在路线里必须连着走,它对外只暴露链首的起点与链尾的终点,
所以收缩成一条「超边」
。 链中间被穿过的点进一次、出一次,度数天然平衡,收缩后不需要再为它们记账。 - 环:它已经在自己那批边上闭合成圈。而
必须是覆盖全部 条边的单环, 所以闭合轨道能成立的前提是它自己就吞掉全部边——这时整条路线被唯一确定, 只要路口 在这条回路上(即有边与 关联)就输出 TAK。 一旦出现两条闭合轨道,或者闭合轨道之外还残留着链,轨道就会在自己的边集里绕圈、 永远接不上其余街道,直接NIE。
收缩图上判欧拉回路。 全是链时,收缩得到多重图
- 平衡条件:每个点出度 = 入度(每条超边给起点一次出、给终点一次入);
- 连通条件:所有带边的点落在同一个弱连通块里(忽略方向)。
满足这两条时,任意一个带边的点都可以当作路线起点(回路可以整体旋转),
所以"从
下面用题面样例走一遍。片段是 1 5 6、3 4 3、4 3 6 4、5 6 2。
| 片段 | 逼出的后继指定 |
|---|---|
没有冲突,也没有闭合轨道。粘合结果是三条链(
| 超边 | 起点 | 终点 |
|---|---|---|
| 1 | 2 | |
| 1 | 3 | |
| 4 | 1 | |
| 3 | 4 | |
| 2 | 1 |
逐点检查:TAK。
再看冲突长什么样:若同时给出 1 2 3 和 1 2 4,边 nxt[1->2] 被两次赋了不同值,立刻 NIE——这正是数据点 problem3 的构造。
代码
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-07 20:32
# update_at: 2026-10-07 20:32
import sys
from collections.abc import Iterator
NONE = -1 # 哨兵:不存在的前驱 / 后继 / 街道编号一律用它,含义只在这一行解释
# 类型别名(Python 3.12+ 的 type 语句),相当于 C++ 的 using / typedef
type IntList = list[int] # 一整族按街道编号下标的数组
type SuperEdges = tuple[IntList, IntList] # 收缩后超边族的(起点序列, 终点序列)
def contract_chains(m: int, eu: IntList, ev: IntList, nxt: IntList, prv: IntList) -> SuperEdges | None:
"""把被片段逼成一串的街道收缩成超边,返回 (起点序列, 终点序列);无解时返回 None。
片段逼出的是 succ(街道) = 必须紧跟的那条街道,无冲突时每条街道至多一个后继而
至多一个前驱,所以粘合关系分解成「链」和「环」。链整块连着走,对外只暴露链首
起点与链尾终点,收缩成一条超边;环则必须吞掉全部 m 条街道(succ 本身是覆盖全部
街道的唯一大环),此时回路已被唯一确定,收缩成一条落在环上某点的自环。
"""
unit_of = [NONE] * m
tails: IntList = []
heads: IntList = []
for i in range(m): # 链:从没有被逼出前驱的街道起步
if prv[i] != NONE or unit_of[i] != NONE:
continue
unit_id, e = len(tails), i
while True:
unit_of[e] = unit_id
if nxt[e] == NONE:
break
e = nxt[e]
tails.append(eu[i]) # 链首所在点给一条出边
heads.append(ev[e]) # 链尾所在点给一条入边
# 剩下每条街道都被逼出了后继,它们的 nxt 构成闭合轨道(succ 的闭合块)。succ 必须是
# 覆盖全部 m 条街道的单环,所以轨道只能有一条且吞掉全部街道;两条轨道、或轨道之外
# 还残留着链,都会让轨道在自己的街道集合里绕圈,接不上其余街道。
orbits = 0
for i in range(m):
if unit_of[i] != NONE:
continue
orbits += 1
if orbits > 1:
return None
unit_id, e = len(tails), i
covered = 0
while True:
unit_of[e] = unit_id
covered += 1
e = nxt[e]
if e == NONE or e == i:
break
if covered != m: # 轨道没能吞掉全部街道
return None
tails.append(eu[i]) # 整图就是这条回路,收缩成一条落在环上某点的自环
heads.append(eu[i])
return tails, heads
def start_reachable(n: int, din: IntList, dout: IntList, adj: list[IntList]) -> bool:
"""有街道的点是否都落在同一个连通块里;接不进同一条回路的街道永远走不到。"""
start = next((v for v in range(1, n + 1) if din[v] or dout[v]), 1)
seen = bytearray(n + 1)
seen[start] = 1
stack = [start]
while stack:
for w in adj[stack.pop()]:
if not seen[w]:
seen[w] = 1
stack.append(w)
return all(seen[v] for v in range(1, n + 1) if din[v] or dout[v])
def solve() -> None:
data: Iterator[int] = iter(map(int, sys.stdin.buffer.read().split()))
n, m = next(data), next(data) # 岔路口数、街道数
base = n + 1 # (a,b) 的唯一编码 a*base+b,题面保证街道不重复
eu: IntList = [0] * m # 街道起点,下标即街道编号
ev: IntList = [0] * m # 街道终点
id_of: dict[int, int] = {}
deg1 = 0 # 路口 1 的关联度数:为 0 时邮递员寸步难行
for i in range(m):
a, b = next(data), next(data)
eu[i], ev[i] = a, b
id_of[a * base + b] = i
deg1 += (a == 1) + (b == 1)
nxt: IntList = [NONE] * m # 被片段逼出的后继
prv: IntList = [NONE] * m # 被片段逼出的前驱
stamp: IntList = [0] * m # stamp[e] == 当前片段编号 → 这条街道在本片段里已走过
t = next(data) # 片段数
for f in range(1, t + 1):
k = next(data) # 片段长度
if k < 1:
continue
prev_vertex, prev_edge = next(data), NONE
for _ in range(k - 1):
cur = next(data)
e = id_of.get(prev_vertex * base + cur, NONE) # 片段要求走的这条街道
if e == NONE: # 片段引用了一条不存在的街道
print("NIE")
return
if stamp[e] == f: # 同一条街道在一个片段里要求走两次
print("NIE")
return
stamp[e] = f
if prev_edge != NONE:
conflict = nxt[prev_edge] not in (NONE, e) or prv[e] not in (NONE, prev_edge)
if conflict: # 一条街道被两个片段逼着接不同的后继 / 前驱
print("NIE")
return
nxt[prev_edge], prv[e] = e, prev_edge
prev_edge, prev_vertex = e, cur
units = contract_chains(m, eu, ev, nxt, prv)
if units is None:
print("NIE")
return
tails, heads = units
din: IntList = [0] * (n + 1) # 收缩图上每点的入度
dout: IntList = [0] * (n + 1) # 收缩图上每点的出度
adj: list[IntList] = [[] for _ in range(n + 1)]
for a, b in zip(tails, heads): # 超边只给两端点加度数,链中间穿过的点进一次出一次
dout[a] += 1
din[b] += 1
adj[a].append(b) # 只判弱连通,两个方向都要能走
adj[b].append(a)
balanced = all(din[v] == dout[v] for v in range(1, n + 1)) # 欧拉回路的度数条件
on_route = deg1 > 0 or m == 0 # 路线必须从路口 1 出发,1 得真的关联着街道
print("TAK" if balanced and on_route and start_reachable(n, din, dout, adj) else "NIE")
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-07 20:32
* update_at: 2026-10-07 20:32
*/
// 一本通 1737《邮递员》正式解:
// 回路是闭合的,按环状顺序读它的边序列 e_1..e_m(succ(e_i) = e_{i+1},下标模 m)。
// 每个片段 v1..vk 要求 succ((v_j,v_{j+1})) = (v_{j+1},v_{j+2}),于是片段把若干条边
// "粘"成一串:每条边至多被逼出一个后继、一个前驱,被迫接两个就无解。
// 粘合关系是部分单射,必然分解成「链」和「环」:
// · 环——它在 succ 里已经自成闭合块,而 succ 是覆盖全部 m 条边的唯一大环,
// 所以要么不存在环,要么这个环就吞掉全部边(此时回路被唯一确定,只需路口 1 在环上);
// · 链——整条链在回路里必须连着走,收缩成一条「超边」,只保留链首起点与链尾终点。
// 收缩后的多重图上存在经过每条超边一次的闭合路线 ⟺ 逐点入度=出度 且带边的点弱连通;
// 路线可以旋转到任意一个被访问到的点起头,所以还要保证路口 1 真的在路线上。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 50005; // 岔路口数上限
const int MAXM = 200005; // 街道数上限
struct Edge {
int u; // 街道起点
int v; // 街道终点
};
struct KeyedEdge {
ll key; // 街道 (a,b) 的唯一编码 a*(n+1)+b,用于二分查找
int id; // 街道编号
};
bool operator<(const KeyedEdge& x, const KeyedEdge& y) {
return x.key < y.key;
}
Edge edge[MAXM];
KeyedEdge keyed[MAXM];
ll cntEdge; // 街道条数 m,findEdge 的二分右界
int nxtEdge[MAXM]; // nxtEdge[i] = 被片段逼着紧接在街道 i 后面走的那条街道,-1 表示没有
int prvEdge[MAXM]; // prvEdge[i] = 被逼着紧排在街道 i 前面的那条街道,-1 表示没有
int stamp[MAXM]; // stamp[i] == 当前片段编号,说明街道 i 已在本片段里用过(同弧走两次无解)
int unitOfEdge[MAXM]; // 街道 i 归属的超边编号,-1 表示还没归属
int unitTail[MAXM]; // 超边的起点
int unitHead[MAXM]; // 超边的终点
int din[MAXN]; // 收缩图上每个点的入度
int dout[MAXN]; // 收缩图上每个点的出度
int deg1; // 路口 1 在原图里的关联度数,为 0 时邮递员寸步难行
char vis[MAXN]; // 弱连通搜索的访问标记,只有 0/1,用 char 省内存
vector<int> adj[MAXN]; // 收缩图邻接表(无向,只用来判弱连通)
// 逐字符快读:最坏一份输入接近 6MB、上百万个整数,格式化读入太慢
ll readInt() {
int c = getchar();
while (c != -1 && c <= ' ') c = getchar();
if (c == -1) return -1;
ll x = 0;
while (c > ' ') {
x = x * 10 + (c - '0');
c = getchar();
}
return x;
}
// 在按 key 排好序的街道表里二分查找编码为 key 的街道,找不到返回 -1
int findEdge(ll key) {
int lo = 0, hi = (int)cntEdge - 1, res = -1;
while (lo <= hi) {
int mid = (lo + hi) >> 1;
if (keyed[mid].key == key) {
res = keyed[mid].id;
break;
}
if (keyed[mid].key < key) lo = mid + 1;
else hi = mid - 1;
}
return res;
}
int main() {
// nxtEdge / prvEdge / unitOfEdge 用 -1 当"不存在"的哨兵,
// 全局数组默认全是 0,必须先整体置成 -1
memset(nxtEdge, -1, sizeof(nxtEdge));
memset(prvEdge, -1, sizeof(prvEdge));
memset(unitOfEdge, -1, sizeof(unitOfEdge));
ll n = readInt();
ll m = readInt();
cntEdge = m;
for (ll i = 0; i < m; i++) {
ll a = readInt();
ll b = readInt();
edge[i].u = a; // a,b ≤ n ≤ 50000
edge[i].v = b;
if (a == 1 || b == 1) deg1++;
keyed[i].key = a * (n + 1) + b; // 数据保证 (a,b) 只出现一次,编码不冲突
keyed[i].id = i;
}
sort(keyed, keyed + m);
ll t = readInt(); // 片段数
for (ll f = 1; f <= t; f++) {
ll k = readInt();
if (k < 1) continue;
ll prevVertex = readInt();
int prevEdgeId = -1;
for (ll i = 1; i < k; i++) {
ll cur = readInt();
int e = findEdge(prevVertex * (n + 1) + cur); // 片段要求走的这条街道
if (e == -1) { // 片段引用了不存在的街道
printf("NIE\n");
return 0;
}
if (stamp[e] == f) { // 同一条街道在一个片段里要走两次,回路做不到
printf("NIE\n");
return 0;
}
stamp[e] = f;
if (prevEdgeId != -1) {
// 街道 prevEdgeId 后面被迫接两条不同的街道,或街道 e 前面被迫接两条
bool conflict = (nxtEdge[prevEdgeId] != -1 && nxtEdge[prevEdgeId] != e) ||
(prvEdge[e] != -1 && prvEdge[e] != prevEdgeId);
if (conflict) {
printf("NIE\n");
return 0;
}
nxtEdge[prevEdgeId] = e;
prvEdge[e] = prevEdgeId;
}
prevEdgeId = e;
prevVertex = cur;
}
}
// 分解粘合关系:先从每条"没有被逼出前驱"的街道出发走完整条链
int unitCnt = 0;
for (int i = 0; i < (int)m; i++) {
if (prvEdge[i] != -1 || unitOfEdge[i] != -1) continue;
int e = i;
while (true) {
unitOfEdge[e] = unitCnt;
if (nxtEdge[e] == -1) break;
e = nxtEdge[e];
}
unitTail[unitCnt] = edge[i].u; // 链首所在点给一条出边
unitHead[unitCnt] = edge[e].v; // 链尾所在点给一条入边,这一对端点就是收缩出的超边
unitCnt++;
}
// 剩下的街道每条都被逼出了后继,它们的 nxt 构成闭合轨道(succ 的闭合块)。
// succ 必须是覆盖全部 m 条边的单环,所以闭合轨道只能有一条且吞掉全部边;
// 存在两条轨道、或轨道之外还有链时,轨道会在自己的边集内绕圈,接不上其余街道。
int orbitCnt = 0, orbitEdges = 0;
for (int i = 0; i < (int)m; i++) {
if (unitOfEdge[i] != -1) continue;
orbitCnt++;
if (orbitCnt > 1) { // 已经出现第二条轨道,拼不成一条回路
printf("NIE\n");
return 0;
}
int e = i;
while (true) {
unitOfEdge[e] = unitCnt;
orbitEdges++;
e = nxtEdge[e];
if (e == -1 || e == i) break;
}
unitCnt++;
}
if (orbitCnt > 0) {
// 整张图就是这一条闭合回路,回路已被唯一确定:路口 1 在这条回路上即可起头
printf(orbitEdges == (int)m && deg1 > 0 ? "TAK\n" : "NIE\n");
return 0;
}
// 全是链:收缩成超边后,只给两端点加度数(链中间被穿过的点进一次出一次,天然平衡)
for (int i = 0; i < unitCnt; i++) {
int a = unitTail[i], b = unitHead[i];
dout[a]++;
din[b]++;
adj[a].push_back(b);
adj[b].push_back(a);
}
for (int v = 1; v <= (int)n; v++) {
if (din[v] != dout[v]) { // 有向图存在欧拉回路的必要条件
printf("NIE\n");
return 0;
}
}
// 弱连通:带边的点要落在同一个连通块里,否则那些街道接不进同一条回路
static int que[MAXN];
int qh = 0, qt = 0;
int start = 1;
for (int v = 1; v <= (int)n; v++)
if (din[v] > 0 || dout[v] > 0) { start = v; break; }
vis[start] = 1;
que[qt++] = start;
while (qh < qt) {
int u = que[qh++];
for (size_t j = 0; j < adj[u].size(); j++) {
int w = adj[u][j];
if (!vis[w]) {
vis[w] = 1;
que[qt++] = w;
}
}
}
for (int v = 1; v <= (int)n; v++) {
if ((din[v] > 0 || dout[v] > 0) && !vis[v]) {
printf("NIE\n");
return 0;
}
}
// 路线可以旋转到任意一个被访问过的点起头,所以只要路口 1 关联着街道就一定能从 1 出发
printf(deg1 > 0 || m == 0 ? "TAK\n" : "NIE\n");
return 0;
}复杂度
- 时间:读入
;把「顶点对 」定位到边编号,C++ 版把 条边 按编码 排序后二分,片段每走一步一次二分,共 ;Python 版用 dict把编码直接映射到边号, 这一步是。粘合、链/环收缩、度数统计、连通搜索都是 。 合计 ;在 、 下余量充足。 - 空间:
nxt、prv、stamp、unitOfEdge各,度数数组与邻接表 , 总计 。 - 实测:C++ 在最大的
problem10(、 、 、 ) 上 0.17 s / 峰值约 8 MB;Python 同点 0.44 s。两者都远离 1 s / 256 MB 的限制。 - 与 C++ 解法的关系:
main.cpp与main.py是同一算法的两种落地, 差别只在"顶点对边编号"这一步用二分还是用哈希,整体复杂度同阶。
总结
- 把"依次经过"读成"指定后继":题面说的是片段要连着走,落到实现上就是对环状后继
的硬性赋值;不理解这一点就会误把它当成"这些边都出现过"的弱约束。 - 粘合关系是部分函数:每条边至多一个后继、一个前驱,所以粘合结果必然是链 + 闭合轨道, 冲突检测退化成一次比对。
- 收缩只保留端点:链中间被穿过的点进一次出一次,天然平衡、不用记账;
这是把长度
的片段压进普通欧拉回路判定的关键。 - 闭合轨道的可行性完全不同:
必须是覆盖全部边的单环,所以闭合轨道 要么吞掉全部边、要么就是无解(两条轨道、或轨道与链并存都不行)。 忽略这一支,只做度数平衡就会放过假解,这是本题与裸欧拉回路判定的实质差别。 - 欧拉回路两条老规矩:出入度相等 + 忽略方向连通(只查带边的点)。
加上"起点是
",就要求路口 确实关联着街道。
图示解析
下图画出「片段 → 粘合 → 链/环分流 → 收缩超边 → 欧拉回路判定」这条主线。
flowchart TD
F["片段 v1..vk"] -->|"succ(vi,vi+1) = (vi+1,vi+2)"| C["粘合 nxt / prv"]
C -->|"同一条边被逼出两个后继"| N["NIE"]
C -->|"无冲突"| P["分解成 链 + 闭合轨道"]
P -->|"闭合轨道 ≥ 2 条,或轨道与链并存"| N
P -->|"唯一轨道吞掉全部边"| O["整条回路已定:看 1 是否关联边"]
O -->|"是"| T["TAK"]
O -->|"否"| N
P -->|"全是链"| S["收缩成超边 (链首起点, 链尾终点)"]
S --> E["收缩图 G'"]
E -->|"每点入度 = 出度?"| Q{"平衡"}
Q -->|"否"| N
Q -->|"是"| R{"带边的点都弱连通,且 1 关联边?"}
R -->|"否"| N
R -->|"是"| T
观察重点有三处:一是左侧两条直奔 NIE 的支路,说明本题判定不止"数度数"一步;
二是中间「收缩成超边」只用到链首起点与链尾终点,因为链内部被穿过的点在度数上自平衡;
三是右侧最后一道判定缺一不可——平衡保证能回到起点,弱连通保证所有边都能被走到,
而"1 关联边"保证起点真的能选在路口 1。
关于素材与数据。 本仓库
new_ROJ/problems/1737/下带有数据生成脚本data.py, 10 个测试点由它自造:TAK 点都是"从 1 出发回到 1、线性包含全部片段"的显式构造, NIE 点分别是片段弧缺失、粘合冲突、度数失衡、弱连通断开。因此数据全部落在「链」这一支, 没有构造出与闭合轨道相关的判定点。同目录std.cpp与本文解法在思想上同源, 但它把残余的闭合轨道一律当作自环超边处理,没有检查轨道是否吞掉了全部街道。 能把这个差别区分开的最小反例是:text4 4 4 3 4 2 2 4 3 4 1 4 2 4 3 4片段把
锁成一条闭合轨道,而轨道之外还剩着边 ——轨道在自己的边集里绕圈,永远接不上剩下那条边。 std.cpp判TAK,本文解法判NIE, 穷举小规模欧拉回路的暴力程序确认NIE。本文解法按题面"从第一个路口出发并回到第一个路口" 独立推导,下文的结论均已用该暴力程序对拍验证。