# 1067. Sort with Swap(0,*) (25)

100 ms

32000 kB

16000 B

Standard

CHEN, Yue

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`

```#include <stdio.h>
#define MAX 100005
int a[MAX];
int visit[MAX];

int dfs(int x)
{
int count=0;
while(!visit[x])
{
visit[x]=1;
count++;
x=a[x];
}
return count;
}

int main()
{
int n,j;
scanf("%d",&n);
for(j=0;j<n;j++)
scanf("%d",&a[j]);

int result=0;

for(j=0;j<n;j++)
{
int count=dfs(j);
if(count !=1 && count !=0)
result += count+1;
}

/* 假设所有的环路中都不含0，这是都是默认的count+1次 */
/* 在判断一下是否0会出现在某一个环中 */
if(a[0]!=0)
result -= 2;

printf("%d",result);
}```

66 篇文章34 人订阅

0 条评论

## 相关文章

33160

897110

47450

### SpringMVC启动加载、请求分析

DispatcherServlet其实是一个Servlet,用于初始化各个功能的实现类,比如异常处理、视图处理、请求映射等;且继承了FrameworkServl...

13230

54560

### BZOJ1269: [AHOI2006]文本编辑器editor

Descriptio 这些日子，可可不和卡卡一起玩了，原来可可正废寝忘食的想做一个简单而高效的文本编辑器。你能帮助他吗？ 为了明确任务目标，可可对“文本编辑器...

30170

43280

### Leetcode 210 Course Schedule II 拓扑排序

There are a total of n courses you have to take, labeled from 0 to n - 1. Som...

25850

13420

10930