AcWing 1224. 交换瓶子
原题链接
中等
作者:
两生
,
2023-01-10 16:02:20
,
所有人可见
,
阅读 128
import java.util.Scanner;
public class Main{
static int N = 10010;
static int n;
static int b[] = new int[N];
static boolean st[] = new boolean[N];
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 1; i <= n; i++) b[i] = sc.nextInt();
int cnt = 0; // 记录环数
for(int i = 1; i <= n; i++){
if(!st[i]){ // 如果当前瓶子没有被访问过,即含有该瓶子的环没有被记过数
cnt++; // 环数自增
// 将这个环中的所有瓶子置为true
for(int j = i; !st[j]; j = b[j]){
st[j] = true;
}
}
}
System.out.println(n - cnt); // 所需操作数
sc.close();
}
}