题解：CF1385G Columns Swaps

_pig_ · 2026-10-26 09:22:29 · 题解

不需要并查集二分图基环树……一个略有不同的思路？

先说做法：对于每一个 i，从 a_i 向 b_i 连一条权为 1 的边，从 b_i 向 a_i 连一条权为 0 的边。由于每个点的入度出度和肯定为 2（排除不合法，则每个数出现两次），那么一定是若干个类似环的连通块（自环和二元环也算）。对于每一个环，在上面顺时针或逆时针走一遍，看走过的 0 边的个数和走过的 1 边的个数，取小的，加起来就是答案，方案就是把少的那种边取出来在原数组上对应的位置翻转。

如何理解：首先反转一个位置就是把一组边的 0,1 交换一下。那么这样做相当于把每个环都换成了一个一直走 0/1 都能走一圈的环。以一直走 1 为例，相当于是环上的这些点入度出度都为 1，也就是在原数组上的数全部一上一下，构成一个轮换。

注意一下，自环不用管，因为显然是 a_i=b_i，满足条件；但二元环要注意，会连重边，判的时候注意一下。

//By _pig_&_buta_
//Ciallo～(∠・ω< )⌒★
//#pragma GCC optimize(2)
#include <bits/stdc++.h>
//#define int long long
#define x first
#define y second
#define Testify 2221
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <int, pii> piii;
typedef array <int, 2> arr2;
typedef array <int, 3> arr3;
const double PI = acos (-1);
const double eps = 1e-10;
const int N = 2e5 + 10, M = 2e5 + 10;
//const int mod = 1e9 + 7;
//const int mod = 998244353;
int a[N], b[N], ans, op, cnt[N], sz;
vector <pii> v[N];
vector <int> p;
bool vis[N];
void dfs(int u, int rt, int siz, int cnt, int fa, int fw)
{
    vis[u] = true, sz++;
    for (pii t : v[u])
    {
        int j = t.x, w = (a[t.y] == u);
        if (j == fa && fw == 1 - w) continue;
        if (vis[j] && u != rt)
        {
            cnt += w;
            if (cnt < siz - cnt) op = 1, ans += cnt;
            else op = 0, ans += siz - cnt;
            if (w == op) p.push_back (t.y);
        }
        if (!vis[j])
        {
            dfs (j, rt, siz + 1, cnt + w, u, w);
            if (w == op) p.push_back (t.y);
        }
    }
}
signed main()
{
    cin.tie (0), cout.tie (0);
    ios :: sync_with_stdio (false);
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        for (int i = 1; i <= n; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++;
        for (int i = 1; i <= n; i++) cin >> b[i], cnt[b[i]]++;
        bool flag = false;
        for (int i = 1; i <= n; i++) if (cnt[i] != 2) {flag = true; break;}
        if (flag) {cout << "-1\n"; continue;}
        ans = 0, p.clear ();
        for (int i = 1; i <= n; i++) v[i].clear (), vis[i] = false;
        for (int i = 1; i <= n; i++)
        {
            v[a[i]].push_back ({b[i], i});
            v[b[i]].push_back ({a[i], i});
        }
        for (int i = 1; i <= n; i++)
            if (!vis[a[i]])
            {
                sz = 0, op = -1, dfs (a[i], a[i], 1, 0, 0, 0);
                if (sz == 2 && a[i] == a[v[a[i]][0].y] && a[i] == a[v[a[i]][1].y])
                    p.push_back (v[a[i]][0].y), ans++;
            }
        cout << ans << "\n";
        for (int i : p) cout << i << " ";
        cout << "\n";
    }
    return 0;
}//Ciallo~(∠·ω<)⌒☆