数据结构 10-排序6 Sort with Swap(0, i)C语言

10-排序6 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:

1.  
   Swap(0, 1) => {4, 1, 2, 0, 3}
2.  
   Swap(0, 3) => {4, 1, 2, 3, 0}
3.  
   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:

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

Sample Output:

9

 code

1.  
   # include <cstdio>
2.  
    
3.  
   int data[100010];
4.  
   bool visited[100010];
5.  
    
6.  
   int travCircle(int s)
7.  
   {
8.  
   int current = data[s];
9.  
   int cnt = 1;
10.  
    visited[s] = true;
11.  
    while (current != s)
12.  
    {
13.  
    visited[current] = true;
14.  
    cnt ;
15.  
    current = data[current];
16.  
    }
17.  
    return cnt;
18.  
    }
19.  
     
20.  
    int main(void)
21.  
    {
22.  
    int n;
23.  
    scanf("%d", &n);
24.  
     
25.  
    for (int i = 0; i < n; i) visited[i] = false;
26.  
    for (int i = 0; i < n; i) scanf("%d", &data[i]);
27.  
     
28.  
    int ans = 0;
29.  
    for (int i = 0; i < n; i)
30.  
    {
31.  
    if (visited[i]) continue;
32.  
    int tmp = travCircle(i);
33.  
    if (i == 0)
34.  
    {
35.  
    if (tmp == 1) ans = 0;
36.  
    else ans = (tmp - 1);
37.  
    }
38.  
    else
39.  
    {
40.  
    if (tmp == 1) ans = 0;
41.  
    else ans = (tmp 1);
42.  
    }
43.  
    }
44.  
    printf("%d\n", ans);
45.  
    return 0;
46.  
    }

这篇好文章是转载于：学新通技术网