Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路） · znzryb
## 题目大意
**题目名称**：E. Swap to Rearrange
**题目大意**
给定两个长度为 $n$ 的数组 $a$ 和 $b$。你可以对任意下标 $i$ ($1 \le i \le n$) 执行至多一次操作：交换 $a_i$ 和 $b_i$。
你的目标是通过选择若干个下标进行交换，使得操作结束后，数组 $a$ 变成数组 $b$ 的一个**重排**（即最终数组 $a$ 和最终数组 $b$ 包含完全相同的元素集合，只是顺序可能不同）。
如果可以达成目标，请输出操作次数以及被选择进行交换的下标；如果无法达成，请输出 -1。如果存在多种方案，输出任意一种即可。
**输入格式**
每个测试点包含多组数据。
第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。
对于每个测试用例：
- 第一行包含一个整数 $n$ ($1 \le n \le 10^6$)。
- 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$)。
- 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$ ($1 \le b_i \le n$)。
保证所有测试用例中 $n$ 的总和不超过 $10^6$。
**输出格式**
对于每个测试用例：
- 如果无解，输出 -1。
- 否则，第一行输出操作次数 $s$ ($0 \le s \le n$)。
- 第二行输出 $s$ 个整数，表示被交换的下标（下标从 1 开始）。
**样例输入**
```
4
4
1 1 3 3
2 2 4 4
3
1 2 1
3 3 1
3
1 2 3
2 3 1
4
1 2 2 4
3 1 4 3
```
**样例输出**
```
2
2 4
-1
0
2
3 4
```
**样例解释**
- **第一个测试用例**：
初始时 $a=[1, 1, 3, 3]$，$b=[2, 2, 4, 4]$。
选择下标 2 和 4 进行交换：
- 交换 $a_2$ 和 $b_2$：$a$ 变为 $[1, \mathbf{2}, 3, 3]$，$b$ 变为 $[2, \mathbf{1}, 4, 4]$。
- 交换 $a_4$ 和 $b_4$：$a$ 变为 $[1, 2, 3, \mathbf{4}]$，$b$ 变为 $[2, 1, 4, \mathbf{3}]$。
最终 $a=[1, 2, 3, 4]$，$b=[2, 1, 4, 3]$。此时 $a$ 和 $b$ 都包含元素 $\{1, 2, 3, 4\}$，满足条件。
- **第二个测试用例**：
无论如何操作，都无法使 $a$ 成为 $b$ 的重排，故输出 -1。
- **第三个测试用例**：
不需要任何操作，$a=[1, 2, 3]$，$b=[2, 3, 1]$。两者包含的元素集合均为 $\{1, 2, 3\}$，已经是重排关系。输出 0。
## 思路讲解
::: AI 提示 1
我来给你一些渐进式的提示，从方向性的到具体的：
**提示 1：必要条件**
操作只是在每个位置 $i$ 上决定 $a_i$ 和 $b_i$ 谁归最终的 $a'$、谁归最终的 $b'$。无论怎么操作，每个值在 $a'$ 和 $b'$ 中的**总出现次数不会变**。如果要求 $a'$ 是 $b'$ 的重排（即两者元素完全相同），那么每个值的总出现次数必须满足什么条件？
**提示 2：建图**
对于 $a_i = b_i$ 的位置，交换与否没有影响，可以忽略。重点关注 $a_i \neq b_i$ 的位置。把每个**值**看作图上的**节点**，每个满足 $a_i \neq b_i$ 的下标 $i$ 看作一条连接 $a_i$ 和 $b_i$ 的**边**。思考这张图有什么性质。
**提示 3：度数与目标**
在这张图上，经过提示 1 的分析，你会发现每个节点的度数一定是偶数。对于每条边（即每个下标 $i$），交换与否等价于给这条边选择一个**方向**——决定哪个值分给 $a'$，哪个分给 $b'$。最终的要求等价于：每个节点的出度恰好等于其度数的一半。
**提示 4：经典问题**
在一个所有节点度数都是偶数的无向图上，如何给每条边定向，使得每个节点的入度等于出度？这是一个经典的图论问题，和**欧拉回路**有关。
---
按照这个方向，你应该能把思路串起来了。核心就是把 swap 的决策转化为图上边的定向问题。
:::
我感觉AI唬我呢，左看右看，东看西看，完全没看出这道题目为什么需要用图论。因为说白了，这根本不是一个一一对应的问题，对吧？这和图论有什么关系？无非其实就是要让数量相等呀，这个图论实在难以说有什么联系。所以说，我感觉这个AI其实有点乱写，opus4.6，其实也不过如此吧。
仔细的看了一下，应该这道题就是用图论建模做。我们下面用一张图来说明一下图论建模，它这个图是怎么建的。那为什么这道题目用图文建模呢？我认为这道题目首先不适合使用DP解决，因为你不知道以什么为状态。所以说，用DP解决是不可以，因为状态所需空间太大了，然后，其实我们也没什么工具的，要么就贪心啊，你也很难贪，是吧？所以其实也就图论建模了。
首先呢，我们只关注值，所以说我们所见的图呢，是按值连接的。
[Codeforces Round 1026 (Div. 2)-CF-1026-E. Melody](/2026/02/23/20260223-e1ba2987)
就是看了洛谷的题解，体检上的这个人来说，这道题目和CF 1026的E比较相似。我稍微看了一下CF 1026的题面，应该是解法比较相似，都是建图，按值进行图论建模。
剩下的就是找欧拉回路了，哎，怎么就突然扯到欧拉回路了呢？首先我们肯定要找一个回路嘛，如果一个连通分量中每个点的入度和出度一致，那么就说明该连通分量可以变成，或者说，该连通分量就是由一系列环构成的。当然了，由一系列环构成可能不能辅助我们实现，实际上它就是一个回路。我们可以使用欧拉回路的方法，把图中的每条边都消耗掉，欧拉回路是每条边恰好被遍历过一次，就是每条边都被恰好遍历一次组成的闭合路径，就是欧拉回路。这个和我们所说的由一系列环构成是一样的，其实是一个意思。**存在欧拉回路的这个条件也很简单，就是每个顶点的度数都是偶数，那么一定存在一条欧拉回路**（在联通无向图中）。
::: 求解欧拉图的 horizontal 算法的这个模拟
你画的图我看到了：左边是环 $1\text{-}4\text{-}3\text{-}2\text{-}1$，右边是环 $3\text{-}5\text{-}6\text{-}7\text{-}3$，两个环在顶点 3 相交。共 8 条边。
从顶点 1 出发，逐步执行：
```
操作 stack result
────────────────────────────────────────────────────────
初始 [1] []
1→4 走边(1,4) [1, 4]
4→3 走边(4,3) [1, 4, 3]
3→2 走边(3,2) (3的指针跳过已用的4) [1, 4, 3, 2]
2→1 走边(2,1) [1, 4, 3, 2, 1]
1 没边了，pop [1, 4, 3, 2] [1]
2 没边了，pop [1, 4, 3] [1,2]
3 还有边！3→5 走边(3,5) [1, 4, 3, 5] [1,2]
5→6 走边(5,6) [1, 4, 3, 5, 6]
6→7 走边(6,7) [1, 4, 3, 5, 6, 7]
7→3 走边(7,3) [1, 4, 3, 5, 6, 7, 3]
3 没边了，pop [1, 4, 3, 5, 6, 7] [1,2,3]
7 没边了，pop [1, 4, 3, 5, 6] [1,2,3,7]
6 没边了，pop [1, 4, 3, 5] [1,2,3,7,6]
5 没边了，pop [1, 4, 3] [1,2,3,7,6,5]
3 没边了，pop [1, 4] [1,2,3,7,6,5,3]
4 没边了，pop [1] [1,2,3,7,6,5,3,4]
1 没边了，pop [] [1,2,3,7,6,5,3,4,1]
```
反转 result：
$$
1 \to 4 \to 3 \to 5 \to 6 \to 7 \to 3 \to 2 \to 1
$$
8 条边各走一次，回到起点。
**回退发生在哪里**：走完左边的环 $1 \to 4 \to 3 \to 2 \to 1$ 后，顶点 1 和 2 都没有剩余边了，连续 pop 两次（这就是回退），退到顶点 3。顶点 3 还有边到 5 和 7，于是从 3 继续出发走右边的环。最后反转 result 把右边的环"嵌入"到顶点 3 的位置，拼成完整的欧拉回路。
:::
不过，由于这里我们不需要求欧拉回路，我们只是想要把这个图给建成一个环形的这个嵌套组合，那么实际上是非常简单的。
```cpp
// 开始图论建模
vector<vector<To_id>> g(N+2);
vector<char> vis_edge(N+2);
for (int i=1;i<=N;++i) {
g[A[i]].push_back({B[i],i,0});
g[B[i]].push_back({A[i],i,1});
}
for (int i=1;i<=N;++i) {
if (SZ(g[i])%2!=0) {
cout<<-1<<"\n";
return;
}
}
vector<ll> ans_ls;
// 我们这里不需要求欧拉回路，我们只是想要把这个图给建成一个环形的这个嵌套组合，那么实际上是非常简单的
for (int st_node=1;st_node<=N;++st_node) {
if (g[st_node].empty()) continue;
ll u=st_node;
while (!g[u].empty()) {
auto [to,id,inv]=g[u].back();
g[u].pop_back();
if (vis_edge[id]) {
continue;
}
vis_edge[id]=true;
if (inv) {
ans_ls.push_back(id);
}
u=to;
}
}
sort(all(ans_ls));
cout<<SZ(ans_ls)<<"\n";
for (auto u:ans_ls) {
cout<<u<<" ";
}
cout<<"\n";
```
## AC代码
AC
[https://codeforces.com/contest/2192/submission/363992212](https://codeforces.com/contest/2192/submission/363992212)
::: 源代码
```cpp
/**
* Problem: Swap to Rearrange
* Contest: CodeForces
* Judge: Virtual Judge
* URL: https://vjudge.net/problem/CodeForces-2192E#author=0
* Created: 2026-02-23 00:14:09
* Author: Gospel_rock
* My blog: https://znzryb.com/
*
* 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 debug1d(a) \
cerr << #a << " = ["; \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a) \
cerr << #a << " = [\n"; \
for (int i = 0; i < (int)(a).size(); i++) \
{ \
cerr << " ["; \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j]; \
cerr << "]\n"; \
} \
cerr << "]\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 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;
/*
*
*/
struct To_id {
ll to,id,inv;
};
void Solve() {
ll N;
cin >> N;
vector<ll> A(N+2);
vector<ll> B(N+2);
// map<ll,ll> freqa,freqb;
for (int i=1;i<=N;++i) {
cin>>A[i];
// freqa[A[i]]++;
}
for (int i=1;i<=N;++i) {
cin>>B[i];
// freqb[B[i]]++;
}
do {
vector<ll> sa=A,sb=B;
sort(sa.begin()+1,sa.begin()+N+1);
sort(sb.begin()+1,sb.begin()+N+1);
bool ok=true;
for (int i=1;i<=N;++i) {
if (sa[i]!=sb[i]) {
ok=false;
break;
}
}
if (ok) {
cout<<0<<"\n\n";
return;
}
}while (false);
// 开始图论建模
vector<vector<To_id>> g(N+2);
vector<char> vis_edge(N+2);
for (int i=1;i<=N;++i) {
g[A[i]].push_back({B[i],i,0});
g[B[i]].push_back({A[i],i,1});
}
for (int i=1;i<=N;++i) {
if (SZ(g[i])%2!=0) {
cout<<-1<<"\n";
return;
}
}
vector<ll> ans_ls;
// 我们这里不需要求欧拉回路，我们只是想要把这个图给建成一个环形的这个嵌套组合，那么实际上是非常简单的
for (int st_node=1;st_node<=N;++st_node) {
if (g[st_node].empty()) continue;
ll u=st_node;
while (!g[u].empty()) {
auto [to,id,inv]=g[u].back();
g[u].pop_back();
if (vis_edge[id]) {
continue;
}
vis_edge[id]=true;
if (inv) {
ans_ls.push_back(id);
}
u=to;
}
}
sort(all(ans_ls));
cout<<SZ(ans_ls)<<"\n";
for (auto u:ans_ls) {
cout<<u<<" ";
}
cout<<"\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://codeforces.com/contest/2192/submission/363992212
*/
```
:::