邮递员

GitHub跳转原题关系图返回列表

片段逼出「每条弧的唯一后继」,粘合成链后收缩成超边,再在收缩图上判从路口 1 出发的欧拉回路:逐点入度等于出度且带边的点弱连通。

OJ: roj

题目 ID: 1737

难度:提高+/省选-

标签:图论欧拉回路python

创建: 2026-10-07 20:32

更新: 2026-10-07 20:32

形式化题目

给定有向图 G=(V,E)G=(V,E),V={1,…,N}V=\{1,\dots,N\},每对 (a,b)(a,b) 至多出现一次。再给定 tt 个顶点序列 (片段)v1v2⋯vkv_1 v_2 \cdots v_k,它要求边 (v1,v2),(v2,v3),…,(vk−1,vk)(v_1,v_2),(v_2,v_3),\dots,(v_{k-1},v_k) 在路线里 紧接着依次出现(走过 vivi+1v_i v_{i+1} 之后必须立刻走 vi+1vi+2v_{i+1}v_{i+2},中间不许插别的边)。

求是否存在一条从路口 11 出发、回到路口 11、恰好把每条边各走一次的闭合路线(即欧拉回路), 使每个片段都被完整连续地包含其中。

形式化地:路线是全体 mm 条边的一个排列 e1,…,eme_1,\dots,e_m,令 ei=(si,ti)e_i=(s_i,t_i),要求

ti=si+1  (1⩽i<m),tm=s1=1; t_i = s_{i+1}\;(1 \leqslant i < m), \qquad t_m = s_1 = 1 ;

并定义环状后继 succ(ei)=ei+1\mathrm{succ}(e_i) = e_{i+1}(下标模 mm),要求对每个片段 v1⋯vkv_1\cdots v_k 都有

succ((vj,vj+1))=(vj+1,vj+2)(1⩽j<k−1). \mathrm{succ}\big((v_j, v_{j+1})\big) = (v_{j+1}, v_{j+2}) \qquad (1 \leqslant j < k-1).

注意 succ\mathrm{succ} 是环状的,片段允许跨过路线的收尾相接处。

正解

思路

片段其实是在点名规定后继。 一条闭合路线 e1⋯eme_1 \cdots e_m 定义了唯一的环状后继 succ(ei)=ei+1\mathrm{succ}(e_i)=e_{i+1}(下标模 mm);由于每条边恰好被走一次,succ\mathrm{succ} 是全体 mm 条边上的 一个置换,又是单环——也就是"把全部边串成一个圈"的那种置换。片段 v1⋯vkv_1\cdots v_k 要求的 正是 succ((vj,vj+1))=(vj+1,vj+2)\mathrm{succ}((v_j,v_{j+1}))=(v_{j+1},v_{j+2}),即它硬性指定了某些边的后继是谁。 两条片段若对同一条边指定了不同的后继、或对同一条边指定了不同的前驱,就自相矛盾。

怎么记录这个指定。 对每条边 ee 记 nxt[e]、prv[e]:片段要求 ee 后面紧跟 ff 时令 nxt[e] = f、prv[f] = e。因为 nxt、prv 各自至多有一个值,任何人来改写都要先比对, 不一致立刻判 NIE。同一片段内若同一条边出现两次,也直接 NIE(边只能走一次)。

被指定的边必然分解成「链」和「环」。 nxt 是部分函数,沿 nxt 走只有两种归宿: 走到一条没有后继的边(链),或者绕回自己(环,即闭合轨道)。这两种形状的可行性完全不同:

  • 链:整条链在路线里必须连着走,它对外只暴露链首的起点与链尾的终点, 所以收缩成一条「超边」(s(链首), t(链尾))\big(s(\text{链首}),\,t(\text{链尾})\big)。 链中间被穿过的点进一次、出一次,度数天然平衡,收缩后不需要再为它们记账。
  • 环:它已经在自己那批边上闭合成圈。而 succ\mathrm{succ} 必须是覆盖全部 mm 条边的单环, 所以闭合轨道能成立的前提是它自己就吞掉全部边——这时整条路线被唯一确定, 只要路口 11 在这条回路上(即有边与 11 关联)就输出 TAK。 一旦出现两条闭合轨道,或者闭合轨道之外还残留着链,轨道就会在自己的边集里绕圈、 永远接不上其余街道,直接 NIE。

收缩图上判欧拉回路。 全是链时,收缩得到多重图 G′G'。原问题等价于: G′G' 上是否存在一条恰好经过每条超边一次的闭合路线,且该路线经过路口 11。判据是两条:

  1. 平衡条件:每个点出度 = 入度(每条超边给起点一次出、给终点一次入);
  2. 连通条件:所有带边的点落在同一个弱连通块里(忽略方向)。

满足这两条时,任意一个带边的点都可以当作路线起点(回路可以整体旋转), 所以"从 11 出发"只额外要求路口 11 关联着街道——它必须真的在路线上。

下面用题面样例走一遍。片段是 1 5 6、3 4 3、4 3 6 4、5 6 2。

片段 逼出的后继指定
1 5 61\,5\,6 succ(1→5)=5→6\mathrm{succ}(1\to5)=5\to6
3 4 33\,4\,3 succ(3→4)=4→3\mathrm{succ}(3\to4)=4\to3
4 3 6 44\,3\,6\,4 succ(4→3)=3→6\mathrm{succ}(4\to3)=3\to6,succ(3→6)=6→4\mathrm{succ}(3\to6)=6\to4
5 6 25\,6\,2 succ(5→6)=6→2\mathrm{succ}(5\to6)=6\to2

没有冲突,也没有闭合轨道。粘合结果是三条链(1→5→5→6→6→21\to5\to5\to6\to6\to2、4→3→3→6→6→44\to3\to3\to6\to6\to4) 加四条单边,共 55 条超边:

超边 起点 终点
1→5→5→6→6→21\to5 \to 5\to6 \to 6\to2 1 2
1→31\to3 1 3
4→14\to1 4 1
3→43\to4 3 4
2→12\to1 2 1

逐点检查:11 出 22 入 22,22 出 11 入 11,33 出 11 入 11,44 出 11 入 11, 全部平衡;五个端点 1,2,3,41,2,3,4 彼此可达,路口 11 有边关联。输出 TAK。

再看冲突长什么样:若同时给出 1 2 3 和 1 2 4,边 1→21\to2 被要求后继是 2→32\to3 又是 2→42\to4, nxt[1->2] 被两次赋了不同值,立刻 NIE——这正是数据点 problem3 的构造。

代码

Python 版:

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++ 版(同一算法):

cpp
/**
 * 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;
}

复杂度

  • 时间:读入 O(N+M+∑k)O\big(N + M + \sum k\big);把「顶点对 (a,b)(a,b)」定位到边编号,C++ 版把 MM 条边 按编码 a⋅(N+1)+ba\cdot(N+1)+b 排序后二分,片段每走一步一次二分,共 O(Mlog⁡M+(∑k)log⁡M)O\big(M\log M + (\sum k)\log M\big);Python 版用 dict 把编码直接映射到边号, 这一步是 O(M+∑k)O\big(M + \sum k\big)。粘合、链/环收缩、度数统计、连通搜索都是 O(N+M)O(N+M)。 合计 O(Mlog⁡M+(∑k)log⁡M)O\big(M\log M + (\sum k)\log M\big);在 M⩽2×105M \leqslant 2\times 10^5、 ∑k⩽106\sum k \leqslant 10^6 下余量充足。
  • 空间:nxt、prv、stamp、unitOfEdge 各 O(M)O(M),度数数组与邻接表 O(N+M)O(N+M), 总计 O(N+M)O(N+M)。
  • 实测:C++ 在最大的 problem10(N=5×104N=5\times10^4、M=162370M=162370、t=104t=10^4、∑k≈7.6×105\sum k \approx 7.6\times10^5) 上 0.17 s / 峰值约 8 MB;Python 同点 0.44 s。两者都远离 1 s / 256 MB 的限制。
  • 与 C++ 解法的关系:main.cpp 与 main.py 是同一算法的两种落地, 差别只在"顶点对 →\to 边编号"这一步用二分还是用哈希,整体复杂度同阶。

总结

  • 把"依次经过"读成"指定后继":题面说的是片段要连着走,落到实现上就是对环状后继 succ\mathrm{succ} 的硬性赋值;不理解这一点就会误把它当成"这些边都出现过"的弱约束。
  • 粘合关系是部分函数:每条边至多一个后继、一个前驱,所以粘合结果必然是链 + 闭合轨道, 冲突检测退化成一次比对。
  • 收缩只保留端点:链中间被穿过的点进一次出一次,天然平衡、不用记账; 这是把长度 O(∑k)O(\sum k) 的片段压进普通欧拉回路判定的关键。
  • 闭合轨道的可行性完全不同:succ\mathrm{succ} 必须是覆盖全部边的单环,所以闭合轨道 要么吞掉全部边、要么就是无解(两条轨道、或轨道与链并存都不行)。 忽略这一支,只做度数平衡就会放过假解,这是本题与裸欧拉回路判定的实质差别。
  • 欧拉回路两条老规矩:出入度相等 + 忽略方向连通(只查带边的点)。 加上"起点是 11",就要求路口 11 确实关联着街道。

图示解析

下图画出「片段 → 粘合 → 链/环分流 → 收缩超边 → 欧拉回路判定」这条主线。

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 与本文解法在思想上同源, 但它把残余的闭合轨道一律当作自环超边处理,没有检查轨道是否吞掉了全部街道。 能把这个差别区分开的最小反例是:

text
4 4
4 3
4 2
2 4
3 4
1
4 2 4 3 4

片段把 2→4,  4→3,  3→42\to4,\;4\to3,\;3\to4 锁成一条闭合轨道,而轨道之外还剩着边 4→24\to2 ——轨道在自己的边集里绕圈,永远接不上剩下那条边。std.cpp 判 TAK,本文解法判 NIE, 穷举小规模欧拉回路的暴力程序确认 NIE。本文解法按题面"从第一个路口出发并回到第一个路口" 独立推导,下文的结论均已用该暴力程序对拍验证。