并查集真的是个好东西啊
解题思路
题目大意很简单,就不赘述了。
我们考虑,对于题目所给的序列中的每个数 $a[i]$ ,如果 $a[i]$ 与这个位置本该存在的数 $i$ 不同,那么就向 $a[i]$ 与 $i$ 之间连一条边,那么到最后整个图应该是由若干个环和若干个孤点形成的。孤点代表着该数已经在自己所在的位置,环代表环内的数通过相互交换一定可以回到原位。
这个结论是很好证明的:如果存在一个数,既不属于环,也不属于孤点,那么说明这个数既不在自己的位置,也无法与任意数交换回到自己的位置,这与题目是矛盾的。
那么,由于题目中要求我们需要用任何数与 $0$ 交换做到排序,那么也就是说,对于那些与 $0$ 在同一环内的数,可以直接通过若干次与 $0$ 的交换让他们回到正确的位置。
而对于那些与 $0$ 不在环内的数,我们可以通过一次破环操作:即让 $0$ 与任意一个数交换,从而让 $0$ 替代这个数进入环中,然后做上面的操作,操作结束后再让$0$与这个数交换即可,即破环后再补上。
那么假设一个环有 $k$ 个元素,那么这个环内部的元素互相交换后排序需要 $k-1$ 步操作,破环与补环一共需要$2$步操作。也就是说,如果是 $0$ 所在的环,需要 $k-1$ 步操作;如果不是 $0$ 所在的环,则需要 $k+1$ 步操作。此外,那些孤点不能被算进答案内。
这样子思路就很明朗了,我们需要找出题目所给的序列中多少个环,然后忽略那些已经在正确位置的点,那些不在正确位置的点对答案的贡献为 $1$ ,每个环还有额外的 $1$ 贡献。那么如何找到环的个数呢?当然是并查集了。
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int a[N],p[N];
int find(int x)
{
if (p[x]!=x) p[x]=find(p[x]);
return p[x];
}
int main()
{
cin>>n;
for (int i=0;i<n;i++) p[i]=i;
for (int i=0;i<n;i++)
{
cin>>a[i];
if (a[i]!=i) p[find(a[i])]=find(i);
}
int ans=0;
set<int> st;
for (int i=0;i<n;i++)
{
//如果该点已经在正确的位置则忽略
if (a[i]==i) continue;
//注意 0即使不在正确的位置 它也不会有任何贡献
if (a[i]==0) continue;
if (find(a[i])==find(0)) ans++;
else
{
ans++;
if (a[i]==find(a[i]))
st.insert(find(a[i]));
}
}
cout<<ans+st.size();
return 0;
}