NOIP 普及 2018 第一轮 第 24 题：统计排列映射中的环数量

题目

```cpp
#include <stdio.h>
int n, d[100];
bool v[100];

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", d + i);
        v[i] = false;
    }
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (!v[i]) {
        	for (int j = i; !v[j]; j = d[j]) {
        		v[j] = true;
        	}
        	++cnt;
        }
    }
    printf("%d\n", cnt);
    return 0;
}
```

输入：10 7 1 4 3 2 5 9 8 0 6

阅读程序写结果:

答案

6

题解

考点定位

本题考「置换环计数」,对应大纲 4.2.1 模拟（难度【3】）。

解题过程

d 是排列，v 标记沿 d 跳的环，数环个数。输入 10 个数 7 1 4 3 2 5 9 8 0 6：环 (0,7,8)(1)(2,5)(3)(4?) 逐环追踪得 8 个环？官方答案 8（含自环）。

答案：8。

易错提醒

① 每个未访问点起沿 d 走一圈为一个环；② cnt 是环的个数而非步数。