有 NN 个瓶子，编号 1∼N1∼N，放在架子上。

比如有 55 个瓶子：

2 1 3 5 4

要求每次拿起 22 个瓶子，交换它们的位置。

经过若干次后，使得瓶子的序号为：

1 2 3 4 5

对于这么简单的情况，显然，至少需要交换 22 次就可以复位。

如果瓶子更多呢？你可以通过编程来解决。

输入格式

第一行包含一个整数 NN，表示瓶子数量。

第二行包含 NN 个整数，表示瓶子目前的排列状况。

输出格式

输出一个正整数，表示至少交换多少次，才能完成排序。

数据范围

1≤N≤100001≤N≤10000,

输入样例1：

5
3 1 2 5 4

输出样例1：

3

输入样例2：

5
5 4 3 2 1

输出样例2：

2

 

 

 

 

 

 

 1 //交换瓶子，通过利用环的变化来解决这个题
 2 //因为每个点只会被遍历常数次，所以是O(n)
 3 
 4 
 5 #include<iostream>
 6 #include<cstdio>
 7 #include<cstring>
 8 #include<cmath>
 9 #include<algorithm>
10 using namespace std;
11 
12 const int N=10010;
13 
14 int n;
15 int b[N];   //瓶子
16 bool st[N]; //判重数组，用来帮我们找环
17 
18 int main()
19 {
20     scanf("%d",&n);
21     for(int i=1;i<=n;i++) scanf("%d",&b[i]);
22     
23     int cnt = 0;  //环数
24     for(int i=1;i<=n;i++)
25     {
26         if(!st[i])
27         {
28             cnt++;
29             for(int j=i;!st[j];j=b[j])  //关键
30             {
31                 st[j]=true;
32             }
33         }
34     }
35     cout<<n-cnt<<endl;
36     
37     return 0;
38 }