2025-沈阳站-区域赛-F. The Bond Beyond Time（友谊天长地久）（如何使用 bfs 找一个无弦环）（这种题目，我感觉啊，想要做出来的话，要么就是你的思路得比较好，要么就是还是得写个对拍） · znzryb
## 题目大意
"
Sulfox the fennec fox已经建立了一个迷宫，并邀请他的两个朋友Alice和Bob来尝试。迷宫可以抽象为一个简单的、连通的无向图，其中有$n$个顶点和$m$条边，Alice和Bob在两个指定的不同顶点开始。
在任何玩家移动之前，Sulfox必须为每条无向边选择一个方向，将迷宫变成一个有向图。然后，为了找到对方，两位玩家在定向迷宫内进行回合移动。在每一轮中，他们同时独立行动，不留下任何标记或沟通；相反，他们采取“最愚蠢”的策略：
- 如果玩家当前位于一个具有一个或多个出边的顶点，则他们会任意穿越一个出边到相邻顶点；
- 否则，如果他们当前的顶点没有出边，则他们将停留在该顶点。
作为对自己迷宫设计技能感到自豪的Sulfox，希望将通道定向，以便Alice和Bob永远不会相遇。鉴于无向图和Alice和Bob的起始顶点，请帮助Sulfox定向每条边，使得无论Alice和Bob如何在每一轮中做出选择，他们永远不会在任何一轮结束时占据同一顶点。如果不存在这样的定向，请报告。"
## 思路讲解
我记得是这样子的，**只要两个玩家所在顶点不直接相连**，就简单了，**所有连着两个点的边全部指向这两点**，可以把这两个玩家封死。
两个玩家所在顶点直接相连，就找最小的环，所有其他点（边）指向这个环，避免两个玩家离开这个环。
**我们需要两次 bfs 实现：**
这一部分 bfs 实现，负责这个找到包含 $X → Y$ 的环（这个相对容易），如果知道到了，直接输出答案即可。
```cpp
for (int i=1;i<=1;++i) {
g[X].erase(find(all(g[X]),Y));
g[Y].erase(find(all(g[Y]),X));
queue<ll> q;
vector<char> vis(N + 2);
vis[X] = true;
q.push(X);
vector<ll> parent(N + 2);
while (!q.empty()) {
auto u=q.front();
q.pop();
if (vis[Y]) {
break;
}
for (auto to:g[u]) {
if (vis[to]) continue;
vis[to]=true;
parent[to]=u;
q.push(to);
}
}
if (!vis[Y]) {
break;
}
cout<<"Yes\n";
vector<ll> cycle_ls;
for (ll node=Y;node!=X;node=parent[node]) {
edge_ls.erase(lower_bound(all(edge_ls),
pair{min(node,parent[node]),max(node,parent[node])}));
cycle_ls.push_back(node);
cout<<parent[node]<<" "<<node<<"\n";
}
{
edge_ls.erase(lower_bound(all(edge_ls),
pair{X,Y}));
cycle_ls.push_back(X);
cout<<Y<<" "<<X<<"\n";
}
sort(all(cycle_ls));
for (auto [u,v]:edge_ls) {
if (binary_search(all(cycle_ls),u) ) {
cout<<v<<" "<<u<<"\n";
}else if (binary_search(all(cycle_ls),v)){
cout<<u<<" "<<v<<"\n";
}else {
cout<<u<<" "<<v<<"\n";
}
}
return;
}
```
如果没有包含 $X\to Y$ 的这个环，就从 $X$ 出发，随便找一个这个无弦环即可。
**为什么需要这两个部分呢？**
只要我们在第一阶段排除这样子的包含 $X\to Y$ 的这个环，我们**找到的环上的点的边就不会和** $Y$ **相连。**（可以避免出现一些奇奇怪怪的情况）
```cpp
if (isout==false){
g[X].push_back(Y);
g[Y].push_back(X);
// 没有边权，可以直接使用bfs得到最小环。
queue<ll> q;
vector<char> vis(N + 2);
vis[X] = true;
q.push(X);
vector<ll> parent(N + 2);
// 我们找的环，不仅可以包含这个 X - Y 这条边，也可以不包含 X-Y 这条边
// 只要把 X，Y 诱导的我们的环上即可
ll st_ed_cycle = 0, another_pa_st_ed = 0;
while (!q.empty()) {
auto u = q.front();
q.pop();
if (st_ed_cycle != 0) {
break;
}
for (auto to: g[u]) {
// 排除 parent 点
if (to == parent[u]) continue;
// 一旦只要不是 parent 点就遍历到了，那就是遇到环了
if (vis[to]) {
another_pa_st_ed = u;
st_ed_cycle = to;
continue;
}
vis[to] = true;
parent[to] = u;
q.push(to);
}
}
// 一个环都没有找到？说明图本身是一颗树
if (st_ed_cycle == 0) {
cout << "No\n";
return;
}
vector<ll> order_of_cycle,another_part_of_cycle;
vector<char> vis_route(N+2);
// bfs 还原路径，比较难的地方就是环被砍成了了两半
// 第一段路径，使用这个 parent 还原
for (ll i=st_ed_cycle;i!=X;i=parent[i]) {
order_of_cycle.push_back(i);
vis_route[i]=true;
}
vis_route[X]=true;
order_of_cycle.push_back(X);
ll overlap_node=0;
// 第二段路径还原
for (ll i=another_pa_st_ed;overlap_node=i,!vis_route[i];i=parent[i]) {
vis_route[i]=true;
another_part_of_cycle.push_back(i);
}
reverse(all(order_of_cycle));
order_of_cycle.insert(order_of_cycle.end(),all(another_part_of_cycle));
order_of_cycle.push_back(overlap_node);
// order_of_cycle.insert(find(all(order_of_cycle),overlap_node)+1 , order_of_cycle.front());
// 接下来生成这个序列
vector<pair<ll,ll>> out_ls;
for (int i=0;i<SZ(order_of_cycle)-1;++i) {
ll u=order_of_cycle[i],v=order_of_cycle[i+1];
edge_ls.erase(lower_bound(all(edge_ls),
pair{min(u, v), max(u, v)}));
// cout<<u<<" "<<v<<"\n";
out_ls.emplace_back(u,v);
}
if (!vis_route[Y] ) {
edge_ls.erase(lower_bound(all(edge_ls),
pair{X, Y }));
vis_route[Y]=true;
// cout<<Y<<" "<<X<<"\n";
out_ls.emplace_back(Y,X);
}
// for (ll u=overlap_node,v=order_of_cycle.front();false;) {
// edge_ls.erase(lower_bound(all(edge_ls),
// pair{min(u, v), max(u, v)}));
// // cout<<u<<" "<<v<<"\n";
// out_ls.emplace_back(u,v);
// }
for (auto [u,v]:edge_ls) {
if (vis_route[u] ) {
// cout<<v<<" "<<u<<"\n";
out_ls.emplace_back(v,u);
}else if (vis_route[v]){
// cout<<u<<" "<<v<<"\n";
out_ls.emplace_back(u,v);
}else {
// cout<<u<<" "<<v<<"\n";
out_ls.emplace_back(u,v);
}
}
cout<<"Yes\n";
for (auto [u,v]:out_ls) {
cout<<u<<" "<<v<<"\n";
}
}
```
## AC代码
AC
[https://qoj.ac/submission/2005037](https://qoj.ac/submission/2005037)
::: 源代码
```cpp
/**
* Problem: The Bond Beyond Time
* Contest: QOJ
* Judge: Virtual Judge
* URL: https://vjudge.net/problem/QOJ-14945
* Created: 2026-02-04 14:54:31
* Author: Gospel_rock
*
* Powered by AutoCp https://github.com/Pushpavel/AutoCp
*/
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);
ll lT,testcase;
/*
*
*/
void Solve() {
ll N, M, X, Y;
cin >> N >> M >> X >> Y;
// if (testcase==23) {
// cerr<<N<<" "<<M<<" "<<X<<" "<<Y<<"\n";
// }
tie(X, Y) = pair<ll, ll>{min(X, Y), max(X, Y)};
vector<vector<ll> > g(N + 2);
vector<pair<ll, ll> > edge_ls;
for (int i = 1; i <= M; ++i) {
ll u, v;
cin >> u >> v;
// if (testcase==23) {
// cerr<<u<<" "<<v<<"\n";
// }
g[u].push_back(v);
g[v].push_back(u);
edge_ls.emplace_back(min(u, v), max(u, v));
}
sort(all(edge_ls));
if (binary_search(all(edge_ls), pair<ll, ll>{X, Y})) {
bool isout=false;
for (int i=1;i<=1;++i) {
g[X].erase(find(all(g[X]),Y));
g[Y].erase(find(all(g[Y]),X));
queue<ll> q;
vector<char> vis(N + 2);
vis[X] = true;
q.push(X);
vector<ll> parent(N + 2);
while (!q.empty()) {
auto u=q.front();
q.pop();
if (vis[Y]) {
break;
}
for (auto to:g[u]) {
if (vis[to]) continue;
vis[to]=true;
parent[to]=u;
q.push(to);
}
}
if (!vis[Y]) {
break;
}
cout<<"Yes\n";
vector<ll> cycle_ls;
for (ll node=Y;node!=X;node=parent[node]) {
edge_ls.erase(lower_bound(all(edge_ls),
pair{min(node,parent[node]),max(node,parent[node])}));
cycle_ls.push_back(node);
cout<<parent[node]<<" "<<node<<"\n";
}
{
edge_ls.erase(lower_bound(all(edge_ls),
pair{X,Y}));
cycle_ls.push_back(X);
cout<<Y<<" "<<X<<"\n";
}
sort(all(cycle_ls));
for (auto [u,v]:edge_ls) {
if (binary_search(all(cycle_ls),u) ) {
cout<<v<<" "<<u<<"\n";
}else if (binary_search(all(cycle_ls),v)){
cout<<u<<" "<<v<<"\n";
}else {
cout<<u<<" "<<v<<"\n";
}
}
return;
}
// cout<<"No\n";
// return;
if (isout==false){
g[X].push_back(Y);
g[Y].push_back(X);
// 没有边权，可以直接使用bfs得到最小环。
queue<ll> q;
vector<char> vis(N + 2);
vis[X] = true;
q.push(X);
vector<ll> parent(N + 2);
// 我们找的环，不仅可以包含这个 X - Y 这条边，也可以不包含 X-Y 这条边
// 只要把 X，Y 诱导的我们的环上即可
ll st_ed_cycle = 0, another_pa_st_ed = 0;
while (!q.empty()) {
auto u = q.front();
q.pop();
if (st_ed_cycle != 0) {
break;
}
for (auto to: g[u]) {
if (to == parent[u]) continue;
if (vis[to]) {
another_pa_st_ed = u;
st_ed_cycle = to;
continue;
}
vis[to] = true;
parent[to] = u;
q.push(to);
}
}
// 一个环都没有找到？说明图本身是一颗树
if (st_ed_cycle == 0) {
cout << "No\n";
return;
}
vector<ll> order_of_cycle,another_part_of_cycle;
vector<char> vis_route(N+2);
for (ll i=st_ed_cycle;i!=X;i=parent[i]) {
order_of_cycle.push_back(i);
vis_route[i]=true;
}
vis_route[X]=true;
order_of_cycle.push_back(X);
ll overlap_node=0;
for (ll i=another_pa_st_ed;overlap_node=i,!vis_route[i];i=parent[i]) {
vis_route[i]=true;
another_part_of_cycle.push_back(i);
}
reverse(all(order_of_cycle));
order_of_cycle.insert(order_of_cycle.end(),all(another_part_of_cycle));
order_of_cycle.push_back(overlap_node);
// order_of_cycle.insert(find(all(order_of_cycle),overlap_node)+1 , order_of_cycle.front());
// 接下来生成这个序列
vector<pair<ll,ll>> out_ls;
for (int i=0;i<SZ(order_of_cycle)-1;++i) {
ll u=order_of_cycle[i],v=order_of_cycle[i+1];
edge_ls.erase(lower_bound(all(edge_ls),
pair{min(u, v), max(u, v)}));
// cout<<u<<" "<<v<<"\n";
out_ls.emplace_back(u,v);
}
if (!vis_route[Y] ) {
edge_ls.erase(lower_bound(all(edge_ls),
pair{X, Y }));
vis_route[Y]=true;
// cout<<Y<<" "<<X<<"\n";
out_ls.emplace_back(Y,X);
}
// for (ll u=overlap_node,v=order_of_cycle.front();false;) {
// edge_ls.erase(lower_bound(all(edge_ls),
// pair{min(u, v), max(u, v)}));
// // cout<<u<<" "<<v<<"\n";
// out_ls.emplace_back(u,v);
// }
for (auto [u,v]:edge_ls) {
if (vis_route[u] ) {
// cout<<v<<" "<<u<<"\n";
out_ls.emplace_back(v,u);
}else if (vis_route[v]){
// cout<<u<<" "<<v<<"\n";
out_ls.emplace_back(u,v);
}else {
// cout<<u<<" "<<v<<"\n";
out_ls.emplace_back(u,v);
}
}
cout<<"Yes\n";
for (auto [u,v]:out_ls) {
cout<<u<<" "<<v<<"\n";
}
}
} else {
cout << "Yes\n";
for (auto [u,v]: edge_ls) {
if (u == X || u == Y) {
cout << v << " " << u << "\n";
} else if (v == X || v == Y) {
cout << u << " " << v << "\n";
} else {
cout << v << " " << u << "\n";
}
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif
cin >> lT;
for (testcase=1;testcase<=lT;++testcase)
Solve();
return 0;
}
/*
AC
https://qoj.ac/submission/2005037
*/
```
:::
## 心路历程（WA，TLE，MLE……）
这道题目的 SPJ 怎么写？
编写这道题 SPJ（Special Judge）的核心难点在于：**如何验证“无论怎么走都遇不到”这一条件**。
因为题目中描述的移动策略是“任意选择一条出边（arbitrarily traverse）”，这意味着玩家的移动是不确定的。你不能只模拟一条路径，而是必须模拟**所有可能的路径**。
### 核心思路：集合模拟（Set Simulation）
要在 SPJ 中解决这个问题，关键点不是记录 Alice 和 Bob “在哪一个点”，而是记录他们**当前可能在哪些点的集合**。
由于 $N \le 300$，我们可以使用 C++ 的 `std::bitset<305>` 来高效地维护这个集合。
---
### SPJ 的具体实现步骤
### 1. 基础校验 (Basic Validation)
首先，必须确保选手输出的图是合法的：
- **边数对应**：选手输出的有向边必须和输入的无向边一一对应（通过 `multiset` 或排序后比对）。
- **点范围**：点的编号在 $1 \dots N$ 之间。
### 2. 状态定义 (The Critical Point)
这是 SPJ 最关键的部分。
- 设 $S_A^{(t)}$ 为第 $t$ 轮结束时，Alice **可能**所在的所有顶点的集合。
- 设 $S_B^{(t)}$ 为第 $t$ 轮结束时，Bob **可能**所在的所有顶点的集合。
**初始状态**：
$S_A^{(0)} = \{Alice_{start}\}, \quad S_B^{(0)} = \{Bob_{start}\}$
### 3. 状态转移 (Transition)
每一轮模拟时，我们需要计算下一轮的集合 $S^{(t+1)}$。规则如下：
对于集合中的每一个点 $u \in S^{(t)}$：
- **情况 A（有出边）**：如果 $u$ 有出边指向 $v_1, v_2, \dots$，那么在下一轮，Alice/Bob 可能会出现在这些邻居中的**任何一个**。将 $\{v_1, v_2, \dots\}$ 全部加入 $S^{(t+1)}$。
- **情况 B（无出边）**：如果 $u$ 没有出边，根据题目规则，玩家停留在原地。将 $u$ 加入 $S^{(t+1)}$。
用位运算表示非常快：
```cpp
next_mask = 0;
for (int u = 1; u <= n; u++) {
if (current_mask.test(u)) { // 如果当前可能在 u
if (adj[u].none()) { // u 没有出边
next_mask.set(u); // 下一轮还在 u
} else { // u 有出边
next_mask |= adj[u]; // 下一轮可能在 u 的所有邻居
}
}
}
```
### 4. 碰撞检测 (Collision Check)
在任何时刻 $t$，如果 Alice 和 Bob 的可能位置集合有**交集**，说明存在一种走法让他们相遇，判为 **WA**。
- 判定条件：`(S_A & S_B).any() == true`
### **5. 终止条件 (Termination)**
**模拟不能无限进行下去。我们有两个终止条件：**
1. **相遇：检测到交集，直接** **`quitf(_wa, ...)`****。**
1. **死循环（安全）：****如果当前的“状态对”** $(S_A, S_B)$ **曾经出现过，说明我们进入了一个循环，而且在这个循环中没有发生碰撞。那么继续跑下去也不会碰撞。此时判为 AC。**
- **使用** **`set<pair<string, string>> history`** **记录** **`bitset`** **的状态。**
---
### 完整的 SPJ 代码结构 (基于 testlib.h)
这是一个标准的写法，你可以直接参考：
```cpp
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 305;
int main(int argc, char* argv[]) {
registerTestlibCmd(argc, argv);
int t = inf.readInt(); // 读取测试用例数
while (t--) {
int n = inf.readInt();
int m = inf.readInt();
int startA = inf.readInt();
int startB = inf.readInt();
// 1. 读取标准输入的边 (用于校验)
multiset<pair<int, int>> edges;
for (int i = 0; i < m; i++) {
int u = inf.readInt();
int v = inf.readInt();
if (u > v) swap(u, v);
edges.insert({u, v});
}
string ja = ans.readToken(); // Jury's answer
string pa = ouf.readToken(); // Participant's answer
if (ja != pa) {
quitf(_wa, "Answer mismatch! Expected %s, found %s", ja.c_str(), pa.c_str());
}
if (pa == "No") continue; // 如果是 No，且 Jury 也是 No，这组过了
// 2. 建图 & 校验选手输出的边
vector<bitset<MAXN>> adj(n + 1);
vector<bool> has_outgoing(n + 1, false);
for (int i = 0; i < m; i++) {
int u = ouf.readInt();
int v = ouf.readInt();
// 校验边是否存在于原图中
int u_chk = u, v_chk = v;
if (u_chk > v_chk) swap(u_chk, v_chk);
auto it = edges.find({u_chk, v_chk});
if (it == edges.end()) {
quitf(_wa, "Edge %d->%d invalid or used twice", u, v);
}
edges.erase(it);
// 建图
adj[u].set(v);
has_outgoing[u] = true;
}
// 3. 核心模拟逻辑
bitset<MAXN> curA, curB;
curA.set(startA);
curB.set(startB);
// 状态记忆化，防止死循环超时
set<pair<string, string>> visited_states;
bool ok = true;
int steps = 0;
// 这里的 20000 是一个保险值，实际上如果有环，visited_states 会更早截断
while (steps++ < 20000) {
// Check Collision
if ((curA & curB).any()) {
quitf(_wa, "Alice and Bob meet at step %d", steps);
}
// Check Cycle (Memoization)
string sa = curA.to_string();
string sb = curB.to_string();
if (visited_states.count({sa, sb})) {
// 状态重复，且之前没遇到 WA，说明进入安全循环
break;
}
visited_states.insert({sa, sb});
// Move Alice
bitset<MAXN> nextA;
for (int i = 1; i <= n; i++) {
if (curA[i]) {
if (!has_outgoing[i]) nextA.set(i); // Stay
else nextA |= adj[i]; // Move
}
}
// Move Bob
bitset<MAXN> nextB;
for (int i = 1; i <= n; i++) {
if (curB[i]) {
if (!has_outgoing[i]) nextB.set(i); // Stay
else nextB |= adj[i]; // Move
}
}
curA = nextA;
curB = nextB;
}
}
quitf(_ok, "All test cases passed!");
}
```
### 总结
这道题 SPJ 的精髓在于**不要去想“他们走了哪条路”**，而是利用 $N$ 较小的特点，**并行追踪“他们可能在的所有位置”**。只要这两个位置集合永远不相交，选手的答案就是正确的。