[Algo Beat Contest 017 D] 图博弈

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

把棋子更新转化为长度恰好 n 的反向可达，用有向环加通向 k 的路径构造方案。

OJ: luogu

题目 ID: P17235

难度:普及+/提高-

标签:图论构造有向图博弈

日期: 2026-08-11 07:37

形式化题目

给定一张简单图，每条边最初带有一个方向，但允许在游戏开始前任意改变每条边的方向。初始只有点 $k$ 有棋子。

每一轮同步更新所有点：一个点在下一轮有棋子，当且仅当它存在一条出边指向当前有棋子的点。要求判断是否能选择边方向，使得恰好 $n$ 轮后有棋子的点数为 $1$ ，并在可行时输出一种边方向方案。

思路

先看一个可以直接验证想法的小数据暴力：

首先我们来合并两条规则：合并后的判断结果不依赖节点 $u$ 自己当前有没有棋子，只依赖" $u$ 是否有出边邻居当前有棋子"。下面用两种思维方式推出这个结论。

方式一：穷举四种情况（直觉推理）

把规则按 $u$ 当前状态分四种情况：

$u$ 当前有棋子?	存在出边邻居有棋子?	下一轮 $u$	对应规则
有	否	移除	规则1：“所有出边指向的节点都没有棋子 $\rightarrow$ 移除”
有	是	保留	规则1 的"否则保留"
无	是	放置	规则2：“至少一个有棋子 $\rightarrow$ 放置”
无	否	保持无	规则2 的"否则保持"

看这张表：有棋子的"保留"和无棋子的"放置"，触发条件都是"存在一个出边邻居有棋子"，所以最终规则统一为一句：

next\_state[u] = 1 \iff u \text{ 的某个出边指向的节点 } v \text{ 当前有棋子}

这就是 if (state[v]) next_state[u] = 1; 在做的判断——只要找到任意一个有棋子的出边邻居就把 next_state[u] 置 1。

方式二：一阶谓词逻辑推导（形式化推理）

1. 定义谓词

$P(u)$ ：节点 $u$ 本轮有棋子
$N(u)$ ：节点 $u$ 下一轮有棋子
$E(u)$ ： $\exists v \in Out(u),\ P(v)$ ，即" $u$ 存在一个出边邻居当前有棋子"

2. 把两条规则翻译成逻辑式

规则一（ $u$ 有棋子）：“所有出边指向的节点都没有棋子 $\Rightarrow$ 移除，否则保留”。先明确"所有出边指向的节点都没有棋子"就是 $E(u)$ 的否定：

\neg E(u) \iff \forall v \in Out(u),\ \neg P(v)

于是"否则保留"（即"并非所有出边邻居都没有棋子"）等价于 $\neg(\forall v \in Out(u),\ \neg P(v))$ ，规则一翻译为：

P(u) \rightarrow \big(N(u) \leftrightarrow \neg(\forall v \in Out(u),\ \neg P(v))\big)

继续用量词否定律（德摩根对量词）化简规则一：

\neg(\forall v,\ \neg P(v)) \equiv \exists v,\ P(v) = E(u)

代入规则一得：

P(u) \rightarrow \big(N(u) \leftrightarrow E(u)\big)

规则二（ $u$ 无棋子）：“至少一个出边邻居有棋子 $\Rightarrow$ 放置，否则保持无”：

\neg P(u) \rightarrow \big(N(u) \leftrightarrow E(u)\big)

3. 用排中律 + 析取消去消掉前提

排中律： $P(u) \lor \neg P(u)$ 恒真。

而我们有：

$P(u) \rightarrow (N(u) \leftrightarrow E(u))$
$\neg P(u) \rightarrow (N(u) \leftrightarrow E(u))$

由析取消去规则（ $\frac{A \rightarrow C,\ \neg A \rightarrow C}{C}$ ），无论 $P(u)$ 真假，结论都成立：

N(u) \leftrightarrow E(u)

4. 结论

N(u) \leftrightarrow \exists v \in Out(u),\ P(v)

即" $u$ 下一轮有棋子，当且仅当存在出边邻居本轮有棋子"—— $P(u)$ 自己在推导中被消掉了，这正是代码 if (state[v]) next_state[u] = 1; 的含义。

为什么这里需要排中律？ 直觉完全正确——排中律就是你"if/else 必然覆盖所有情况"这个代码直觉的形式化，两者说的是同一件事。

代码直觉：

cpp

1
2
3
4
5
6
7if (P(u)) {
    N(u) = E(u);
} else {
    N(u) = E(u);
}
// 合并成
N(u) = E(u);

合并的依据是： $P(u)$ 非真即假，if/else 两个分支穷尽了所有可能，没有第三种情况（比如"棋子处于既存在又不存在"的状态）。

而"每个命题要么为真，要么为假，没有第三种"这句话，翻译成逻辑公式就是：

P(u) \lor \neg P(u)

读作：“ $P(u)$ 为真，或者 $P(u)$ 不为真，总有一个成立”——这正是排中律的定义。

所以对应关系是：

代码	逻辑
`if (P(u))`	假设 $P(u)$ 为真
`else`	假设 $\neg P(u)$ 为真
“else 兜底所有剩余情况”	$P(u) \lor \neg P(u)$ 恒真（排中律）
“两个分支穷尽了全部可能”	析取消去的前提

形式化对应：

“if/else 穷尽所有情况” = 排中律： $P(u) \lor \neg P(u)$ 恒真
“if 分支得到 $C$ ” = $P(u) \rightarrow C$
“else 分支得到 $C$ ” = $\neg P(u) \rightarrow C$
“两个分支结论相同，合并” = 析取消去（proof by cases）

完整推导是：

\frac{P(u) \lor \neg P(u) \quad P(u) \rightarrow C \quad \neg P(u) \rightarrow C}{C}

逻辑推导不允许"看代码猜"，每一步都要有依据。排中律提供了"两个分支之外没有别的可能"这个依据。如果把 $P(u)$ 换成三值逻辑（棋子可以处于真、假、未定三种状态），排中律失效，if/else 不再穷尽情况， $N(u) \leftrightarrow E(u)$ 就不一定成立——这时合并是错误的。写代码时其实已经默默用了排中律，只是没意识到；形式化推导把它从直觉变成明确的前提。

同时更新的逻辑对应：一轮中 $N$ 全部由同一份 $P$ 计算，对应"每个节点同时执行"；若边算边覆盖 $P$ ，就相当于在同一个量词求值中混入了 $N$ ，违反规则语义。

cpp

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104/**
 * 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-08-11 07:37
 * update_at: 2026-08-12 09:47
 */
// brute.cpp：小数据暴力解，把每条边是否反转看成 01 选择序列来递归枚举。
// 只适合 n,m 很小的数据（如 Subtask 1 的 n,m <= 15）验证与对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20;
const int MAXM = 20;

int n, m, k;             // n 个节点、m 条边、棋子初始所在的节点 k
int eu[MAXM], ev[MAXM];  // 第 i 条有向边：起点 eu[i]，终点 ev[i]
int choose_edge[MAXM];   // choose_edge[i] 表示第 i 条边是否反转：0 保持原方向，1 反转
int answer_found;        // 是否已经找到一组合法方案
int answer_choose[MAXM]; // 找到的合法方案中每条边的反转选择（0/1）
vector<int> adj[MAXN];   // 反转后的邻接表：adj[u] 保存 u 的所有出边指向的节点

// 检查当前完整选择序列 choose_edge[1..m] 对应的图，进行 n 轮游戏后是否恰好剩 1 枚棋子。
bool check_answer() {
    for (int u = 1; u <= n; u++) adj[u].clear();

    // 按 choose_edge 决定是否交换边的两端，建出反转后的邻接表
    for (int i = 1; i <= m; i++) {
        int u = eu[i], v = ev[i];
        if (choose_edge[i] == 1) swap(u, v); // 反转后 u 变终点、v 变起点
        adj[u].push_back(v);
    }

    bool state[MAXN]; // state[u] = 1 表示节点 u 当前有棋子
    memset(state, 0, sizeof(state));
    state[k] = 1; // 初始棋子放在节点 k

    for (int step = 1; step <= n; step++) {
        // 把两轮规则合并：下一轮节点 u 有棋子 <=> u 有出边指向当前有棋子的节点。
        // 有棋子：只有全部出边指向的节点都没有棋子才移除，否则保留；
        // 无棋子：只要有一个出边指向的节点有棋子就放置。
        bool next_state[MAXN];
        memset(next_state, 0, sizeof(next_state));
        for (int u = 1; u <= n; u++) {
            for (int i = 0; i < (int)adj[u].size(); i++) {
                int v = adj[u][i]; // u 的出边指向 v
                if (state[v]) next_state[u] = 1;
            }
        }
        // 一轮中所有节点同时更新，等全部算完再整体赋值
        for (int u = 1; u <= n; u++) state[u] = next_state[u];
    }

    // 数一下 n 轮后还剩几枚棋子
    int cnt = 0;
    for (int u = 1; u <= n; u++) {
        if (state[u]) cnt++;
    }
    return cnt == 1;
}

// 01 选择序列递归：第 dep 层选择第 dep 条边是否反转。
void dfs(int dep) {
    if (answer_found) return; // 已经找到方案，剪掉剩余分支
    if (dep == m + 1) {       // 一条完整选择序列已生成，统一检查合法性
        if (check_answer()) {
            answer_found = 1;
            for (int i = 1; i <= m; i++) answer_choose[i] = choose_edge[i];
        }
        return;
    }

    // 这一层在决定第 dep 条边的反转状态：0 不反转，1 反转
    for (int x = 0; x <= 1; x++) {
        choose_edge[dep] = x;
        dfs(dep + 1);
        if (answer_found) return;
    }
}

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

    int T;
    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        for (int i = 1; i <= m; i++) cin >> eu[i] >> ev[i];

        answer_found = 0;
        dfs(1); // 枚举全部 2^m 种反转方案

        if (!answer_found) {
            cout << "No\n";
        }
        else {
            cout << "Yes\n";
            for (int i = 1; i <= m; i++) cout << answer_choose[i];
            cout << '\n';
        }
    }
    return 0;
}

这个暴力把每条边是否反转看成一串 01 选择。递归先生成完整的反转方案，到叶子节点再模拟 $n$ 轮，并检查最后棋子数是否为 $1$ 。它能帮助我们确认题意，但复杂度是 $O(2^m \cdot n(n+m))$ ，只能用于小数据。

这题真正的转化在一轮更新规则里。下面先完成这个转化，再按照最有助于发现正解的结构顺序研究各个 Subtask。这个顺序不是机械地按照编号排列，而是：

text

1
2
3
4
5Subtask 1 暴力
-> Subtask 3（AC）：连通单环图
-> Subtask 4（BC）：树
-> Subtask 5（C）：连通一般图
-> Subtask 2、6：一般图

从棋子变化转化为定长有向游走

设第 $t$ 轮后有棋子的点集为 $S_t$ ，初始有

S_0=\{k\}。

根据前面合并后的更新规则，下一轮点 $u$ 有棋子，当且仅当它存在一条出边指向本轮某个有棋子的点：

u\in S_{t+1} \Longleftrightarrow \exists (u\to v),\ v\in S_t。

继续展开 $v\in S_t$ ，就会再得到一条从 $v$ 出发的边。归纳可得：

u\in S_t \Longleftrightarrow u\text{ 存在一条长度恰好为 }t\text{ 的有向游走到 }k。

这里必须使用“游走”而不是“路径”：游走允许重复经过点和边，后面才能在环上绕圈补足步数。

于是原题等价于：

给每条无向边选择一个方向，使得恰好一个点存在长度恰好为 $n$ 的有向游走到 $k$ 。

这一步之后，棋子的动态过程已经消失，问题变成了一个纯粹的图构造问题。

Subtask 3（性质 AC）：先研究连通单环图

性质 A 是 $m=n$ ，性质 C 是图弱连通。两者同时成立时，底层无向图是一个连通单环图：整张图只有一个简单环，其余部分都是挂在环上的树。

既然需要构造一条长度达到 $n$ 的游走，环最自然的用途就是重复绕圈。选择环上距离 $k$ 最近的点 $p$ ，把环定向成一个有向环，再把 $p$ 到 $k$ 的简单路径定向成: 有向环 -> p -> ... -> k

把“有向环加上通向 $k$ 的尾巴”称为核心。环负责重复绕圈，尾巴负责最终到达 $k$ 。

现在需要认真证明：核心为什么恰好产生一个最终棋子，而不是“至少一个”。设：

有向环的长度为 $c$ ；
从出口 $p$ 到 $k$ 的尾巴长度为 $d$ ；
环上点 $u$ 沿环走到 $p$ 需要 $r(u)$ 步，其中 $0\leqslant r(u)<c$ 。

从 $u$ 出发，可以先在环上额外绕 $q$ 圈，再走到 $p$ ，最后沿尾巴到达 $k$ 。总长度为

qc+r(u)+d。

要求它恰好等于 $n$ ，也就是

qc+r(u)+d=n。

先看模 $c$ 的余数：

r(u)\equiv n-d\pmod c。

环上各点对应的 $r(u)$ 恰好分别为 $0,1,\ldots,c-1$ ，所以恰好有一个环上点满足这个同余条件。

还要检查满足同余条件后， $q$ 是否为非负整数。核心由一个长度为 $c$ 的简单环和一条长度为 $d$ 的简单尾巴组成，二者除 $p$ 外没有公共点，因此核心共有 $c+d$ 个点。因为整张图只有 $n$ 个点，所以

c+d\leqslant n，

进而 $n-d\geqslant c$ 。所以满足余数条件的环上点至少可以绕一圈，确实能够凑出恰好 $n$ 步。

在单环图的核心内部，尾巴上的点只能沿尾巴走向 $k$ ，不能返回环上补步数；它到 $k$ 的长度至多为 $d<n$ ，因此不会产生第二枚棋子。于是核心内部恰好只有一个点在第 $n$ 轮有棋子。

单环图上还有挂在核心外的树。为了不让树上的点进入核心，所有树边都从靠近核心的一端指向远离核心的一端：

text

1核心 -> 第一层 -> 第二层 -> ...

这样树上的点无法沿有向边走回核心，更无法到达 $k$ 。树边两端恰好相差一层，这正是 Subtask 5 中"跨层边从 $dist$ 小的一端指向 $dist$ 大的一端"在树上的特例。至此，Subtask 3 的构造完成。

Subtask 4（性质 BC）：树为什么一定无解

性质 B 是 $m=n-1$ ，再加上性质 C 的弱连通，底层无向图就是一棵树。

无论怎样给树边定向，得到的有向图都不含有向环。一次有向游走如果重复经过某个点，重复部分就会形成有向环；所以在有向无环图中，任何有向游走都不能重复点。

图中一共只有 $n$ 个点，因此有向游走的长度最多为 $n-1$ ，不可能存在长度恰好为 $n$ 的有向游走到 $k$ 。所以树一定输出 No。

到这里已经出现了一个很强的猜想：

是否有解，只取决于 $k$ 所在的弱连通分量中是否存在环。

Subtask 5（性质 C）：连通图有很多环怎么办

Subtask 5 保证整张图弱连通，但可能存在很多环。容易卡住的地方是试图同时安排所有环的方向。其实这是构造题，我们只需要找到一种方案，因此没有必要让所有环都参与。

沿用 Subtask 3 的结构即可：

从一般图中抽出一个环作为核心，其余所有结构都设法与核心隔离。

现有代码从 $k$ 开始建立 BFS 树，并在扫描过程中找到第一条连接两个已访问点的非树边。这条非树边与 BFS 树上的两段祖先链构成一个简单环。

为什么使用 BFS 找到的第一条非树边很重要？设这条边的两个端点是 $u,v$ ，它们在 BFS 树中的最低公共祖先是 $w$ 。核心环由

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15              k (BFS 根)
              |
              | 树边
              w  ← u、v 的最低公共祖先（LCA）
             . .
            .   .
           .     .
          u       v
           \     /
            \   /
            u → v（非树边，BFS 扫到的第一条）

   核心环 = u → v（非树边）
         + v → w（树链：v 沿祖先链上溯）
         + w → u（树链：w 沿祖先链下到 u）

组成。这个环内部不会再有弦边：如果两个不相邻的环上点之间还有一条边，那么它不可能是 BFS 树边，否则 BFS 树本身就出现了环；所以它也是一条非树边。环上的点都已经沿 BFS 树被发现，而这条弦至少会在当前非树边之前被某个更早出队的环上点扫描到，与“当前边是第一条被发现的非树边”矛盾。

同理， $w$ 到根节点 $k$ 的树链内部没有跨过中间点的额外边，环与这条树链之间也没有额外连接；否则这样的边同样会是一条更早被扫描到的非树边。因此整个“环加尾巴”核心的内部边，恰好就是构造所使用的环边和树链边，没有额外捷径。

把环按上述顺序定向后，环上每个点到出口的距离模 $c$ 仍然各不相同。

在这个环上选 BFS 深度最小的点 $p$ 。对当前基本环而言，这个点正是前面的最低公共祖先 $w$ 。因为 BFS 根是 $k$ ， $p$ 到 $k$ 的树链就是一条最短路径，并且这条树链与环除 $p$ 外没有公共点。环和这条树链的并集构成核心，并按有向环 -> p -> ... -> k定向。核心内部仍然可以使用 Subtask 3 的公式

qc+r(u)+d=n

证明恰好一个环上点贡献最终棋子。

接下来处理所有核心外的边。以核心中的所有点作为多源 BFS 的起点，计算

dist(x)=x\text{ 到核心的无向最短距离}。

以下定向规则作用于所有尚未定向的边；核心内部的环与尾巴已经在前面定向，不适用本清单：

跨层边（两端 $dist$ 不同）：从 $dist$ 小的一端指向 $dist$ 大的一端：
$dist(u)<dist(v)\Longrightarrow u\to v。$
核心点的出边也属此类（一端为 $dist=0$ ），自然指向核心外。
同层边（两端 $dist$ 相同）：任意方向。

自检：定向完成后，每条有向边 $u\to v$ 都应满足 $dist(v)\geqslant dist(u)$ 。

为什么这样就能隔离核心？因为 $dist$ 沿每条有向边单调不减，从核心外（ $dist>0$ ）出发不可能走到 $dist=0$ 的核心；即使同层边形成有向环，也只能停留在该层或者继续远离核心，仍然无法到达 $k$ 。核心点也可能有一条出边通向外围，但游走一旦离开核心， $dist$ 就从 $0$ 变成正数，此后同样无法回到核心中的 $k$ 。因此，所有最终能够到达 $k$ 的有向游走都只能留在核心内部，前面的余数唯一性证明不会被外围结构破坏。

因此，图中有多少个额外环并不重要：只保留一个环作为“计时器”，再让其余边全部无法进入核心即可。

Subtask 2、6：去掉弱连通限制

Subtask 2 只有 $n,m\leqslant 50$ ，却没有特殊图结构， $2^m$ 的方向枚举已经不可行。它实际上是在提前提示：必须放弃枚举方案，寻找和完整数据相同的结构判定。

去掉性质 C 后，整张图可能有多个弱连通分量，但初始棋子只在 $k$ 。不同弱连通分量之间没有边，所以其他分量从一开始就没有棋子，以后也永远不会产生棋子。它们的边可以任意定向。

因此只需要从 $k$ 开始 BFS，检查 $k$ 所在的弱连通分量：

如果 BFS 找不到非树边，说明该分量是一棵树，不存在长度为 $n$ 的有向游走，输出 No；
如果 BFS 找到非树边，就按 Subtask 5 抽出“有向环加尾巴”的核心，再把其余边朝远离核心的方向定向，输出 Yes。

所以完整数据的充要条件是：

$k$ 所在的弱连通分量中存在环。

完整构造步骤

忽略输入边原来的方向，把每条边暂时看成无向边。
从 $k$ 开始 BFS，记录 BFS 树的父亲、父边和深度，并寻找第一条非树边。
如果没有非树边，输出 No。
用非树边和 BFS 树链构造简单环，并把它定向成有向环。
选择环上 BFS 深度最小的点 $p$ ，把 $p$ 到 $k$ 的树路径定向为 $p\to\cdots\to k$ 。
把环与这条路径标记为核心，进行多源 BFS，求所有点到核心的距离。
所有剩余边从距离小的一端指向距离大的一端；同层边以及其他弱连通分量中的边任意定向。
根据最终方向与输入方向是否相同，输出对应的 0/1 字符串。

代码

cpp

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204/**
 * 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-08-11 07:37
 * update_at: 2026-08-12 14:24
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3005;
const int MAXM = 6005;

struct Edge {
    int from;
    int to;
    int answer; // 0：保持输入方向，1：反转，-1：尚未定向
};

struct AdjEdge {
    int to;
    int id;
};

int n, m, k;
Edge edges[MAXM];
vector<AdjEdge> graph[MAXN];

int parentNode[MAXN];
int parentEdge[MAXN];
int depth[MAXN];
int distToCore[MAXN];

int cycleU, cycleV, cycleEdge;

void clearCase() {
    for (int i = 1; i <= n; i++) {
        graph[i].clear();
        parentNode[i] = -1;
        parentEdge[i] = 0;
        depth[i] = 0;
        distToCore[i] = -1;
    }
    cycleU = cycleV = cycleEdge = 0;
}

// 把第 id 条边定向为 u -> v。
void setDirection(int id, int u, int v) {
    edges[id].answer = (edges[id].from == u && edges[id].to == v ? 0 : 1);
}

// 建立以 k 为根的 BFS 树，并找到第一条非树边。
void findCycle() {
    queue<int> q;
    parentNode[k] = 0;
    q.push(k);

    while (!q.empty() && cycleEdge == 0) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < (int)graph[u].size(); i++) {
            int v = graph[u][i].to;
            int id = graph[u][i].id;

            if (parentNode[v] == -1) {
                parentNode[v] = u;
                parentEdge[v] = id;
                depth[v] = depth[u] + 1;
                q.push(v);
            }
            // 简单图没有父子平行边，排除父节点就等价于排除唯一的父边。
            else if (v != parentNode[u]) {
                cycleU = u;
                cycleV = v;
                cycleEdge = id;
                break;
            }
        }
    }
}

int findLca(int u, int v) {
    while (depth[u] > depth[v]) u = parentNode[u];
    while (depth[v] > depth[u]) v = parentNode[v];

    while (u != v) {
        u = parentNode[u];
        v = parentNode[v];
    }
    return u;
}

// 构造“有向环 + 通向 k 的尾巴”。
void buildCore() {
    int exitNode = findLca(cycleU, cycleV);

    // cycleU -> cycleV -> ... -> exitNode -> ... -> cycleU
    setDirection(cycleEdge, cycleU, cycleV);

    int x = cycleV;
    while (x != exitNode) {
        distToCore[x] = 0;
        setDirection(parentEdge[x], x, parentNode[x]);
        x = parentNode[x];
    }

    distToCore[exitNode] = 0;
    x = cycleU;
    while (x != exitNode) {
        distToCore[x] = 0;
        setDirection(parentEdge[x], parentNode[x], x);
        x = parentNode[x];
    }

    // 环的出口沿 BFS 树走向 k。
    x = exitNode;
    while (x != k) {
        distToCore[x] = 0;
        setDirection(parentEdge[x], x, parentNode[x]);
        x = parentNode[x];
    }
    distToCore[k] = 0;
}

// 其余边全部朝远离核心的方向定向。
void directRemainingEdges() {
    queue<int> q;

    for (int i = 1; i <= n; i++) {
        if (distToCore[i] == 0) q.push(i);
    }

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int i = 0; i < (int)graph[u].size(); i++) {
            int v = graph[u][i].to;
            if (distToCore[v] == -1) {
                distToCore[v] = distToCore[u] + 1;
                q.push(v);
            }
        }
    }

    for (int id = 1; id <= m; id++) {
        if (edges[id].answer != -1) continue;

        int u = edges[id].from;
        int v = edges[id].to;

        // 同一弱连通分量内朝远离核心定向；其他分量两端距离都是 -1，方向任意。
        if (distToCore[u] <= distToCore[v]) {
            setDirection(id, u, v);
        }
        else {
            setDirection(id, v, u);
        }
    }
}

void solveCase() {
    findCycle();
    if (cycleEdge == 0) {
        cout << "No\n";
        return;
    }

    buildCore();
    directRemainingEdges();

    cout << "Yes\n";
    for (int i = 1; i <= m; i++) {
        cout << edges[i].answer;
    }
    cout << '\n';
}

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

    int T;
    cin >> T;

    while (T--) {
        cin >> n >> m >> k;
        clearCase();

        for (int i = 1; i <= m; i++) {
            cin >> edges[i].from >> edges[i].to;
            edges[i].answer = -1;

            int u = edges[i].from;
            int v = edges[i].to;
            graph[u].push_back({v, i});
            graph[v].push_back({u, i});
        }

        solveCase();
    }
    return 0;
}

复杂度

第一次 BFS 寻找非树边，沿 BFS 树链提取环和尾巴；第二次多源 BFS 计算各点到核心的距离；最后扫描一次所有边确定方向。

每组数据的时间复杂度为 $O(n+m)$ 。

邻接表、父亲数组、方向数组等占用线性空间，空间复杂度为 $O(n+m)$ 。

总结

这题的第一个关键是把同步更新转化为定长有向游走：第 $t$ 轮点 $u$ 有棋子，当且仅当 $u$ 存在一条长度恰好为 $t$ 的有向游走到 $k$ 。

第二个关键来自构造题思维：一般图中即使有很多环，也不需要全部处理。只抽出一个“有向环加通向 $k$ 的尾巴”作为核心，就能用环上的不同余数保证恰好一个起点走满 $n$ 步。其余边全部朝远离核心的方向定向，从而隔离所有额外结构。

最终，有解当且仅当 $k$ 所在的弱连通分量含环。

图示解析

这张图按照 Subtask 的结构变化，串起从暴力到完整构造的路线：

text

1
2
3
4
5
6
7
8
9
10Subtask 1：枚举每条边是否反转，再模拟 n 轮
`- 观察一轮更新：u 下一轮有棋子 <=> u 有出边指向本轮棋子
   `- 第 n 轮：从 u 存在长度恰好 n 的有向游走到 k
      |- Subtask 3（AC）：单环作为计时器，接一条尾巴到 k
      |  `- qc + r(u) + d = n，模 c 后恰好一个环上起点
      |- Subtask 4（BC）：树中最长有向游走不超过 n-1，无解
      |- Subtask 5（C）：多环图只抽取一个核心环
      |  `- 其他边按 dist 朝远离核心的方向定向
      `- Subtask 2、6：只处理 k 所在弱连通分量
         `- 该分量有环 <=> 有解

读这张图时，先抓住从“棋子状态”到“定长有向游走”的等价转化。之后每个 Subtask 只是在回答两个问题：有没有环可以补步数，以及怎样阻止核心外的点进入这个环。

单环情形给出了核心模型，树的情形给出了无解判定，多环情形则体现了构造题的关键：只保留一个有用结构，主动隔离其他结构。去掉弱连通限制后，也只需关注初始棋子所在的分量。

P17235 [Algo Beat Contest 017 D] 图博弈

题目背景

小 K 曾是一名围棋高手。

题目描述

小 K 获得了一个新的“自走围棋”棋盘！

这个棋盘可以抽象为一张 $n$ 个节点、 $m$ 条边的简单有向图，其中恰好在一个节点 $k$ 上初始放置有棋子。节点编号 $1\sim n$ 。

在棋盘上，有一个游戏共进行恰好 $n$ 轮。每一轮对每个节点同时执行：

若节点有棋子：如果其所有出边指向的节点都没有棋子，则移除该棋子；否则保留。
若节点没有棋子：如果其所有出边指向的节点中至少有一个有棋子，则放置一枚棋子；否则保持无棋子。

显然一般而言，最后会剩下很多棋子。不过小 K 比较黑暗，所以游戏开始前，他希望选择任意若干条边反转方向（当然，可以不反转），使得进行完所有游戏轮数后，图上恰好剩 $1$ 枚棋子。

你的任务求是否存在反转边的方案满足小 K 的要求。若存在则输出方案。

简单有向图指的是这样一张有向图 $G$ ，对于 $G$ 中任意一条边 $(u,v)$ ，有 $u \neq v$ ，并且不存在另外一条边 $(u',v')$ ，满足 $u=u',v=v'$ 或者 $u=v',v=u'$ 。

输入格式

本题有多组测试数据。

第一行一个正整数 $T$ ，表示测试数据组数。

对于每组数据：

第一行个正整数 $n, m, k$ 。
接下来 $m$ 行，每行两个整数 $u, v$ 表示有向边 $u\to v$ 。保证无重边自环。

输出格式

对于每组数据：

若无解输出一行 No。
否则第一行输出 Yes，第二行输出长 $m$ 的字符串，0 保持原方向，1 反转。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2
3
4
5
6
7No
Yes
000
No
Yes
11100
No

说明/提示

【数据范围与约定】

对于所有测试点，保证：

$1\le T\le 10$
$1\le n\le 3 \times 10^3$ ， $0\le m\le 6 \times 10^3$ ， $1\le k\le n$
每个输入图均无重边、无自环
所有测试数据的 $n$ 之和、 $m$ 之和分别不超过 $10^4$

本题开启子任务捆绑。

Subtask	特殊性质	分值
1	$n,m\le 15$	20
2	$n,m\le 50$	10
3	AC	20
4	BC	10
5	C	20
6	无特殊限制	20

性质 A： $m=n$
性质 B： $m=n-1$
性质 C：图是弱连通的

定义一张有向图 $G$ 是弱连通的，当且仅当对于任意 $G$ 上的满足 $u \neq v$ 的点对 $(u,v)$ ，存在这样一种 $G$ 上的边集的子集 $S_{u,v}$ ，使得在反转 $S_{u,v}$ 中的所有有向边的方向后，存在一条从 $u$ 到 $v$ 的有向路径。

保证 SPJ 的用时远小于 0.1 秒。

[Algo Beat Contest 017 D] 图博弈

目录

形式化题目

思路

从棋子变化转化为定长有向游走

Subtask 3（性质 AC）：先研究连通单环图

Subtask 4（性质 BC）：树为什么一定无解

Subtask 5（性质 C）：连通图有很多环怎么办

Subtask 2、6：去掉弱连通限制

完整构造步骤

代码

复杂度

总结

图示解析