交换瓶子
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int st[N];
int main()
{
int n, cnt = 0;
cin >> n;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
}
for(int i = 1; i <= n; i ++)
{
if(!st[i])
{
for(int j = i;!st[j];j = a[j])
{
st[j]=true;
}
cnt ++;
}
}
cout <<n - cnt <<endl;
}
按照阳历一来解释的话，就是3->2,2->1,1->3，他们之间形成了一个闭环。4->5,5->4，这也是一个闭环。
交换1和3会发现闭环变为3->2,2->3，1->1。要将k个环分解成n个， 所以是n-k
华为工作强度 847人发布
投递旷视等公司10个岗位 >
