AcWing 1224. 交换瓶子
原题链接
中等
作者:
大海呀大海
,
2020-07-07 10:45:35
,
所有人可见
,
阅读 587
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010;
int n;
int a[N];
bool st[N];
int main(){
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 ++;//记录环的个数
//cout << st[i] << ' ' << i << endl;
for (int j = i; !st[j]; j = a[j])//中间的判断是用来判重的,for会一直将这个环搜完的
//所以在下面相关的i,st[i] 都是查询过的
st[j] = true;
}
//cout << endl;
//一个环中结点的个数为k,那么只要进行k-1次操作就可以将一个闭环变成k个自环
//一共有n个点,cnt个环,每个环可做的操作为k-1次,当环是一个时,就是1-1=0次操作
//所以n个点,要做的操作只用n-cnt
cout << n - cnt << endl;
return 0;
}
}