摘要
Title: 1224. 交换瓶子
Tag: 贪心、并查集
Memory Limit: 64 MB
Time Limit: 1000 ms

1224. 交换瓶子

题意

有 N 个瓶子，编号 1∼N，放在架子上。
比如有 5 个瓶子：
2 1 3 5 4
要求每次拿起 2 个瓶子，交换它们的位置。
经过若干次后，使得瓶子的序号为：
1 2 3 4 5
对于这么简单的情况，显然，至少需要交换 2 次就可以复位。
如果瓶子更多呢？你可以通过编程来解决。
思路

与此题比较类似：Acwing 1215. 小朋友排队
区别：
- 此题为任意交换
- 另题为相邻交换
贪心
采用贪心的策略从前往后遍历，如果它和下标不同，那么必须把它换到和它下标相同，即往后遍历找相同即可，复杂度 $O(n^2)$
并查集
详细证明证明交换次数为 $n - k$ ，k为环的个数，建图方式为，自己和自己该在的地方存在的数相连
如 3 1 2 4 5，则 3->2

代码

贪心

'''
Author: NEFU AB-IN
Date: 2022-03-29 11:19:18
FilePath: \ACM\Acwing\1224.py
LastEditTime: 2022-03-29 11:54:55
'''
N = int(1e6 + 10)
st = [0] * N

n = int(input())
a = list(map(int, input().split()))
a = [0, *a]

ans = 0
for i in range(1, n + 1):
    if a[i] != i:
        for j in range(i + 1, n + 1):
            if a[j] == i:
                a[i], a[j] = a[j], a[i]
        ans += 1

print(ans)

并查集

'''
Author: NEFU AB-IN
Date: 2022-03-29 12:40:53
FilePath: \ACM\Acwing\1224.1.py
LastEditTime: 2022-03-29 12:43:46
'''
N = int(1e6 + 10)
fa = [i for i in range(N)]


def find(x):
    if x != fa[x]:
        return find(fa[x])
    return fa[x]


n = int(input())
a = list(map(int, input().split()))
a = [0, *a]

for i in range(1, n + 1):
    x = find(a[i])
    y = find(a[a[i]])
    fa[x] = y

ans = 0
for i in range(1, n + 1):
    if fa[i] == i:
        ans += 1

print(n - ans)

1224. 交换瓶子

题意

思路

代码