Q. Z 小花的狗窝

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

Z 小花给村里的 $n$ 只小狗按照 $1,2,3,\ldots,n$ 的顺序进行了编号，他为每只小狗都准备了一个温馨的狗窝，狗窝同样也按照 $1,2,3,\ldots,n$ 的顺序进行了编号。但是村里的小狗天生倔脾气，如果编号为 $i$ 的小狗住在编号为 $i$ 的狗窝里，它就会不高兴！出于无奈，Z 小花只好给某些不高兴的小狗交换狗窝。他想知道，最少要交换几次，才能使所有的狗都不会不高兴。

输入格式

第 1 行输入一个整数 $T$ ，表示共 $T$ 组数据。
每组数据包含两行，第一行为一个整数 $n$ ，表示有 $n$ 只小狗和狗窝。
第二行有 $n$ 个整数 $a_1,a_2,\ldots,a_n$ ，为 $1\sim n$ 的某种排列，表示 $i$ 号小狗住在 $a_i$ 号狗窝中。

输出格式

一共 $T$ 行，每行一个整数，表示最少的交换次数。

5
2
2 1
3
1 2 3
5
1 2 5 4 3
4
1 2 4 3
10
10 2 1 3 6 5 4 7 9 8

数据范围

$1 \le T \le 1000$ ， $1 \le n \le 10^5$ 。

浙江省第三届智力运动会编程项目（U8）

未参加

状态: 已结束
规则: XCPC
题目: 20
开始于: 2026-8-30 10:00
结束于: 2026-8-30 11:00
持续时间: 1 小时
主持人: Atuer
参赛人数: 0