7439. 交换轮数排序 (Swap Round Sorting)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 交换轮数排序 (Swap Round Sorting) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 给你一个长度为 $n$ 的数组，其中包含 $1, 2, \dots, n$ 的一个排列。你的任务是使用“交换轮数”对数组进行排序。在每一轮交换中，你可以选择任意多对互不相交的元素位置，并交换每对位置上的元素。 你的任务是求出最少需要的交换轮数，并展示在每一轮中应如何选择这些位置对。 ## 输入格式 第一行包含一个整数 $n$：数组的大小。 第二行包含 $n$ 个整数 $x_1, x_2, \dots, x_n$：初始排列。 ## 输出格式 首先输出一个整数 $k$：最少的交换轮数。 接下来，对于每一轮，先输出该轮的交换次数，然后输出该轮中每次交换的两个位置下标。你可以输出任何一种合法方案。 ## 输入输出样例 ### 输入 #1 ```text 5 5 2 1 3 4 ``` ### 输出 #1 ```text 2 2 1 3 4 5 1 3 5 ``` ## 说明/提示 初始数组为 $[5, 2, 1, 3, 4]$。 - 第 $1$ 轮后，交换了 $(1,3)$ 和 $(4,5)$，数组变为 $[1, 2, 5, 4, 3]$。 - 第 $2$ 轮后，交换了 $(3,5)$，数组变为 $[1, 2, 3, 4, 5]$。 ### 数据规模与约定 - $1 \le n \le 2 \cdot 10^5$