AT_abc233_f [ABC233F] Swap and Sort

思路

一眼可以把两个可以交换的数之间建一条边，显然在一个连通块里面的元素可以两两之间交换。

由于是排列，每一个元素 $i$ 最终的位置是 $i$。

考虑将元素从小到大放置，令 $ad_i$ 表示当前 $i$ 元素的位置。

现在我们想让 $i$ 换到 $i$ 位置上，并且想使用最小的步数（因为有 $5 \times 10^5$ 的限制），那么在图上找到 $i$ 到 $ad_i$ 的最短路即可。

需要注意的是，我们让 $i$ 换到 $i$ 位置后，需要将它们在图之中的点换回去。

Code

#include <bits/stdc++.h>
#define fst first
#define snd second
#define re register

using namespace std;

typedef pair<int,int> pii;
const int N = 2e5 + 10,M = 1010,inf = 1e9 + 10;
int n,m;
int ty[M][M],p[N],ad[N],d[N];
pii arr[N];
bool vis[N];
vector<int> ans,g[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void bfs(int s){
    fill(d + 1,d + n + 1,inf);
    fill(vis + 1,vis + n + 1,false);
    queue<int> q;
    q.push(s); vis[s] = true;
    while (!q.empty()){
        int u = q.front(); q.pop();
        for (int v:g[u]){
            if (vis[v]) continue;
            d[v] = d[u] + 1;
            vis[v] = true; q.push(v);
        }
    }
}

int main(){
    n = read();
    for (re int i = 1;i <= n;i++) ad[p[i] = read()] = i;
    m = read();
    for (re int i = 1;i <= m;i++){
        int a,b; a = read(),b = read();
        g[a].push_back(b); g[b].push_back(a);
        arr[i] = {a,b}; ty[a][b] = ty[b][a] = i;
    }
    for (re int i = 1;i <= n;i++){
        if (i == ad[i]) continue;
        bfs(i);
        if (d[ad[i]] == inf) return puts("-1"),0;
        int u = ad[i];
        vector<int> t;
        while (u != i){
            for (int v:g[u]){
                if (d[v] + 1 == d[u]){
                    swap(p[u],p[v]);
                    t.push_back(ty[u][v]);
                    ans.push_back(ty[u][v]);
                    u = v; break;
                }
            }
        }
        if (t.size() >= 2){
            for (re int j = t.size() - 2;~j;j--){
                int x = t[j];
                swap(p[arr[x].fst],p[arr[x].snd]);
                ans.push_back(x);
            }
        }
        for (re int j = 1;j <= n;j++) ad[p[j]] = j;
    }
    if (ans.size() > 5e5) puts("-1");
    else{
        printf("%d\n",ans.size());
        for (int x:ans) printf("%d ",x);
    }
    return 0;
}