AcWing 1224. 交换瓶子-python注释详解版
原题链接
中等
作者:
嶋野的狂犬
,
2024-09-26 19:54:11
,
所有人可见
,
阅读 1
n=int(input())
a=list(map(int,input().split()))
# 最开始,若某一点不在自己位置上,
# 则这个点指向占领他应在位置上的那个点,从而会形成小于n个环
# 最后时,每个点都在自己应该在的位置上,所以都会指向自己
# 从而形成了n个环
# 交换环内的两个点,则此环会裂成两个
# 交换两个环的两个点,则两个环会合成一个
# 故为了产生n个环,我们只对环内进行操作
# 对任意一个环来说,若环里有n个元素,则需要操作n-1次就能拆分成n个环
# 判重数组,检测当前元素是否被标记
st=[0]*n
# 统计环的数目
cnt=0
for i in range(n):
# 如果没有形成单个环
if st[i]==0:
# 则环数加1
cnt+=1
# 标记该环包含的所有元素
j=i
# 停止条件为所有环内元素都被标记
while(st[j]==0):
# 标记当前元素
st[j]=1
# 指向当前元素的下一个元素
# 由于题目中元素从1开始,数组从0开始
# 我们状态数组存储的是标号-1个元素的状态
j=a[j]-1
# 通过简单数学推导,我们不难发现,操作次数=总元素个数-环的个数
print(n-cnt)