题解：AT_abc436_e [ABC436E] Minimum Swap

· · 题解

::::info[第一问]

给出一个非有序的排列，如何用最少的交换次数使其有序？

举个例子，我们给出一个排列 p：

位置 1 2 3 4 5 6
元素 3 2 4 1 6 5

对于元素 i，现在位于位置 x，他需要去到的是位置 i。我们可以用边来表示这样的关系，也就是将每一组位置 x 和元素 i 连边。对于这一组数据，结果为：

这个图告诉了我们什么信息？

位置 1 上的元素要去位置 3，位置 3 上的元素要去位置 4，位置 4 上的元素要去位置 1。

位置 5 上的元素要去位置 6，位置 6 上的元素要去位置 5。

位置 2 上的元素不需要动。

发现了什么吗？对于一个环 C，我们只需要进行 |C|-1 次交换操作，就能完成对环内元素的排序。所有环排完序，整个排列就有序了。

::::

::::info[第二问]

我们按照上面的建图方法建图，即对于所有 i，建边 (i,P_i)。

第一次的交换操作，可以选择任意一个环中的任意两个元素进行交换，设建图后有 m 个环（不含单点），于是答案就是：

\sum_{i=1}^m {|C_i|\choose2}

虽然意义上是有向图，但是由于题目性质，这里可以当无向图来建。使用并查集来维护。

时间复杂度 O(n\alpha(n))。 ::::

::::success[代码]

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
using namespace std;
const int N=3e5+10;
int n,x,fa[N],siz[N];
long long ans; 
int find(int x){return (x^fa[x])?fa[x]=find(fa[x]):fa[x];}
void merge(int u,int v){
    int fu=find(u),fv=find(v);
    if(fu!=fv) fa[fu]=fv,siz[fv]+=siz[fu];
}
int main(){
    scanf("%d",&n);
    rep(i,1,n) fa[i]=i,siz[i]=1;
    rep(i,1,n) scanf("%d",&x),merge(x,i);
    rep(i,1,n) if(fa[i]==i) ans+=1ll*(siz[i]-1)*siz[i]/2ll;
    cout<<ans;
    return 0;
}

::::