1067 Sort with Swap(0, i)

Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:

Swap(0, 1) => {4, 1, 2, 0, 3}
Swap(0, 3) => {4, 1, 2, 3, 0}
Swap(0, 4) => {0, 1, 2, 3, 4}

Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.

Input Specification:

Each input file contains one test case, which gives a positive N (≤105) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.

Output Specification:

For each case, simply print in a line the minimum number of swaps need to sort the given permutation.

Sample Input:

10
3 5 7 2 6 4 9 0 8 1

Sample Output:

9

题意

现在给定一个序列，需要我们只用 swap(0,*) 操作即其他数只能与 0 进行交换，将该序列变成一个升序序列。

思路

这道题可以转换成图的做法，拿题目例子来看，给定一个序列 {3,5,7,2,6,4,9,0,8,1} ，那么我们可以将每个数指向它目前所在的位置，例如 3 目前在 0 的位置即 3->0 ，5 目前在 1 的位置即 5->1 ，可以得到下图：

由于只能和 0 进行交换，当我们把 0 与其环外元素交换时，两个环会合成一个环；而当把 0 与环内元素交换时，又分两种情况，一种是与 0 的 next 元素交换，一种是与不是 0 的 next 元素交换，而第二种得到的结果等于什么都没发生即白操作一次，而第一种就可以使 0 的 next 元素变成自环，例如上面将 0 和 7 进行交换，可以得到下面的结果：

所以这就明朗起来了，具体步骤如下：

1.如果 0 所在环的元素大于 1 ，就先将 0 与它的 next 元素进行交换，每交换一次，0 的 next 元素就会变成一个自环即指向了自己所在的位置。

2.如果 0 所在环只有 0 自己了，就去看看外面是否还有元素个数大于 1 的环。如果有，就将这个环中任意一个元素与 0 进行交换，这样 0 就加入到这个环中了，然后再重复步骤 1 直至环里元素都变成自环。

3.记录上述交换的次数，最后输出最终交换次数。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int p[N];
int n;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int id;
        cin >> id;
        p[id] = i;    //将序列中的元素位置转换成图
    }
    int res = 0;
    for (int i = 1; i < n;)
    {
        //如果0所在环不只1个元素，则将0和它指向的下一个元素进行交换
        while (p[0]) swap(p[0], p[p[0]]), res++;
        //如果当前元素已经在对应位置上即已形成自环，则跳过
        while (i < n && p[i] == i) i++;
        //如果还存在除0所在环外，元素个数大于0的环，则将0加入该环
        if (i < n) swap(p[0], p[i]), res++;
    }
    //输出交换次数
    cout << res << endl;
    return 0;
}