NOIP 提高 2018 第一轮 第 22 题：置换环计数（排列的循环个数）

题目

```c
#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 跳数环。输入 10 个数 7 1 4 3 2 5 9 8 0 6：环 (0,7,6,9? ) 逐环追踪：0→7→8→0（环{0,7,8}）；1→1（自环）；2→5→2（环{2,5}）；3→3（自环）；4→4（自环）；6→6? d[6]=9→9→d[9]=6（环{6,9}）；共 6 个环。

答案：6。

易错提醒

① v[] 防重复计数；② 每个未访问点起沿 d 走一圈计一环。