置換環

作用：求解數組排序元素間所需最小交換次數這類問題。

思想：置換環將每個元素指向其排序后應在的位置，最終首位相連形成一個環（若數字在最終位置，則其自身成環），可知元素之間的交換只會在同一個環內進行，而每個環內的最小交換次數為\(環上元素個數-1\)。

則總交換次數：\(ans = \sum_{i = 1}^n(cyclesize_i-1)=數組長度-環的個數\)

例題1：Problem - D - Codeforces

題意：給定一個長度為$ n(n≤2×10^5)$ 的排列 \(p\)。你可以多次交換排列中的任意兩個數。問，最少多少次交換，可以使得排列中，有且僅有一個逆序對。

思路：利用上面的結論，我們要換的次數是\(n-環數+1\)。但是如果有相鄰的兩個數的話那么可以通過減少一次交換，使得其貢獻出一個逆序對。次數的交換次數為\(n-環數-1\)

code:

int n, p[N], vis[N];
map<int, bool>ring;//記錄環
bool flag = 0;
void dfs(int u) {
    if (vis[u]) return;
    vis[u] = 1;
    ring[u] = 1;
    int v = p[u];// u -> v
    if (ring[u - 1] || ring[u + 1])flag = 1;//記錄是否有相鄰的兩個點
    dfs(v);
}
void slove() {
    cin >> n;
    for (int i = 1; i <= n; i++)vis[i] = 0;
    for (int i = 1; i <= n; i++)cin >> p[i];
    int cur = 0;
    flag = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            cur++;
            ring.clear();
            dfs(i);
        }
    }
    if (flag)cout << n - cur - 1 << endl;
    else cout << n - cur + 1 << endl;
}

例題2：Problem - E - Codeforces

題意：給你一個排列(\(1～n\))，這個排列被認為是簡單的需要滿足下面其中一個條件：

對于每一個\(i(1\le i\le n)\)

• \(p_i = i\)
• \(p_{p_i} = i\)

問你最少交換多少次使得這個排列是簡單的。

思路：考慮置換環。

對于\(i\rightarrow p[i] \rightarrow p[p[i]] \rightarrow p[p[p[i]]] \rightarrow ... \rightarrow i\) 這樣子的會構成一個環。需要滿足條件的話，環的長度需要\(\ge 2\)。即，最后這個數列轉化為圖一定是若干個自環和若干個兩數環所組成的圖。

對于環長度\(\le 2\)的，要進行交換操作讓環長度變短。我們發現讓\(p[p[i]] = i\)比讓\(p[i] = i\)更優，為什么呢？

我們設\(mp[i]\)為數值為\(i\)的下標。以\(2,3,4,1\)為例：

\(mp[1] = 4\)，\(p[1] = 2\)，我們想讓\(p[p[1]] = 1\)即\(p[2] = 1\),那么\(p[mp[1]] = p[2]\)，即\(p[4] = 3\)

交換完一次之后變成了\(2,1,4,3\)。同時更新\(mp[1] = 2,mp[3] = 4\)

這樣必定可以一次修改兩個數，是優于\(p[i]\)改成\(i\)的，那么對于環長度為\(size\)的，交換次數為\(\lfloor\dfrac{size-1}{2} \rfloor\)。

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n + 1);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n + 1, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};


int main()
{
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        DSU d(n);
        for(int i = 1;i <= n; i++)
        {
            int x; cin>>x;
            d.merge(i,x);
        }
        set<int>s;
        for(int i = 1;i <= n; i++){
            d.f[i] = d.find(i);
            s.insert(d.f[i]);
        }

        int ans = 0;
        for(auto x : s)
        {
            ans += (d.siz[x]-1)/2;
        }

        cout<<ans<<"\n";
    }
    return 0;
}

或者直接模擬上述過程也是可以的：

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        map<int,int>mp;
        vector<int>p(n+1);
        for(int i = 1;i <= n; i++){
            cin>>p[i];
            mp[p[i]] = i;
        }
        int ans = 0;
        for(int i = 1;i <= n; i++)
        {
            if(p[i] == i || p[p[i]] == i)
                continue;
            int s = mp[i],t = p[i];
            swap(p[s],p[t]);
            mp[p[s]] = s;
            mp[p[t]] = t;
            ans++;
        }
        cout<<ans<<"\n";
        
    }

    return 0;
}

//2 3 4 1
//2 1 4 3

//2 3 4 5 1
//2 1 4 5 3
//2 1 4 3 5