AcWing 1224. 交换瓶子 ( 画图-> 环 :环的数量)
原题链接
中等
作者:
北孤_YCL
,
2024-04-09 19:06:17
,
所有人可见
,
阅读 1
// 任意两个位置的瓶子可以交换
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 10010;
int b[N];
bool st[N]; // 判重数组
int n;
// 瓶子的编号 : 1~n
// 环
// 有序状态下,n个数,一共有n个环 , 编号为i的瓶子,在第i个位置
// 如果有k个环,则需要交换n-k次
// 关键问题: 找到一共有多少个环
int main()
{
cin >> n;
for (int i = 1; i <= n; i++)
cin >> b[i];
// 找环的数量
int k = 0;
for (int i = 1; i <= n; i++) // 从前往后遍历
{
if (!st[i]) // 如果当前点没有被找过, 说明这个点在一个新的环里
{
k++;
for (int j = i; !st[j]; j = b[j]) // 接下里把这个点能到的所有点都标记一下
st[j] = true;
}
}
cout << n - k << '\n';
return 0;
}