置换群 环

1. 交换瓶子
   有 N 个瓶子，编号 1∼N，放在架子上。

比如有 5 个瓶子：

2 1 3 5 4
要求每次拿起 2 个瓶子，交换它们的位置。

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

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

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

输入格式
第一行包含一个整数 N，表示瓶子数量。

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

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

数据范围
1≤N≤10000,

输入样例1：
5
3 1 2 5 4
输出样例1：
3
输入样例2：
5
5 4 3 2 1
输出样例2：
2

本题特点:

比如 
节点 3 1 2 5 4
位置 1 2 3 4 5
y总讲的是通过位置映射节点形成的环(反过来看也是一样的)
上面的数列有两个环(1的位置是3,3的位置是2,2的位置是1,1的位置又是3 故形成一个环) 3 -> 2 -> 1 -> 3,
同理另一个环为 5 -> 4 -> 5;

有两种情况(性质):
    情况一：
        交换同一个环内的点可以分裂成两个环 例如交换节点 
        3 和 1,那么位置1的节点就变成了1,而位置2的节点就
        变成了3,根据 通过位置映射节点形成的环就会将一个环
        形成了1 -> 1,3 -> 2 -> 3 两个环
    情况二:
            交换不同环中的点可以合并两个环

    本题解题思路:如果有k个环在n个位置上边,如果想形成n个环(n个环意思就是每个节点都是一个自己和自己相连的自闭环),根据情况一,如果想分裂成n个环就最少分裂 n-k 次,本题即解

复杂度O(n)

#include<iostream>

using namespace std;
const int N = 10000 + 10;
int a[N];
bool st[N];
int main(){
    int n;
    cin >> n;

    for(int i = 1;i <= n;i++) cin >> a[i];

    int cnt = 0;
    for(int i = 1;i <= n;i++){
        if(!st[i]){
            cnt ++;
            for(int j = i;!st[j];j = a[j])
            st[j] = true;
        }
    }

    cout << n - cnt << endl;

    return 0;

}

个人思路代码O(n^2)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N = 10000 + 10;

int a[N],b[N];

int main(){
    int n;
    cin >> n;
    for(int i = 1;i <= n;i++){
      cin >> a[i];
    } 
    int res = 0;
    for(int i = 1;i <= n;i++){
        if(i != a[i]){
            for(int j = 1;j <= n;j++){
                if(i == a[j]){
                    swap(a[i],a[j]);
                    res++;
                }

            }
        }
    }
    cout << res;
    return 0;


}