题目描述

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

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

经过若干次后，使得瓶子的序号为：1 2 3 4 5

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

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

样例

5
3 1 2 5 4

3

有用并查集写的吗？

依旧是计算环的数目，只不过是用并查集判环

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e4 + 5;

int fa[N], a[N];

int Find(int x)
{
    return fa[x] == x ? x : fa[x] = Find(fa[x]);
}

int main()
{
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) fa[i] = i;
    int x, y;
    for(int i = 1; i <= n; ++ i) scanf("%d", &a[i]);
    for(int i = 1; i <= n; ++ i)
    {
        x = Find(a[i]), y = Find(i);
        if(x != y) fa[x] = y;
    }
    int ans = 0; 
    for(int i = 1; i <= n; ++i)
        if(fa[i] == i) ans ++;
    printf("%d\n", n - ans);
    return 0;
}

看了Y总的代码，日常怀疑我为啥要写那么复杂？？

(要不是智商不够想不到，我至于写这么多嘛)

来欣赏y总的简洁代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 5;

int g[N];
bool st[N];

int main()
{
    int n; scanf("%d", &n);
    for(int i = 1; i <= n; ++ i) scanf("%d", &g[i]);
    int cnt = 0;
    for(int i = 1; i <= n; ++ i)
    {
        if(!st[i])
        {
            cnt++;
            for(int j = i; !st[j]; j = g[j])
                st[j] = true;
        }
    }
    printf("%d\n", n - cnt);
    return 0;
}