Codeforces Round 1081 (Div. 2)-CF-1081-E. Swap to Rearrange（按值进行图论建模）（欧拉回路）

题目大意

题目名称：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 开始）。

样例输入

样例输出

样例解释

第一个测试用例：
初始时 $a=[1, 1, 3, 3]$ $a = [1, 1, 3, 3]$ ， $b=[2, 2, 4, 4]$ $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

就是看了洛谷的题解，体检上的这个人来说，这道题目和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 的位置，拼成完整的欧拉回路。

不过，由于这里我们不需要求欧拉回路，我们只是想要把这个图给建成一个环形的这个嵌套组合，那么实际上是非常简单的。

// 开始图论建模
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

源代码

/**
 * 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

*/