1067. Sort with Swap(0,*) (25)
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
思路：将序列转换为图，形成键-值关系
例如样例：3 5 7 2 6 4 9 0 8 1
对应的值：0 1 2 3 4 5 6 7 8 9
对应的键：3 5 7 2 6 4 9 0 8 1
发现3类环：
a.元素个数>1，包含0的环：0-7-2-3-0
b.元素个数>1，不包含0的环：1-9-6-4-5-1
c.元素个数==1的环：8
其实一张图无非也就最多存在上述3类环。
对于a：交换次数=环的元素个数-1
对于b：交换次数=环的元素个数+1
对于c：交换次数=0
所以，只要统计元素个数>1的环的情况即可。然后根据这些元素个数>1的环是否包含元素0来计算总的交换次数。
代码如下：
#include<cstdio>
#include<stack>
#include<cstring>
#include<iostream>
#include<stack>
#include<set>
#include<map>
using namespace std;
map<int,int> ha;
bool vis[];
void DFS(int cur,int s){
vis[cur]=true;
if(ha[cur]==s){
return;
}
DFS(ha[cur],s);
}
//统计点的数量>1的环的个数，有0在的换交换次数是个数-1；没有0在的环，交换次数是个数+1
int main(){
//freopen("D:\\INPUT.txt","r",stdin);
int count,n;
scanf("%d",&n);
count=n;
int i,num;
for(i=;i<n;i++){
scanf("%d",&num);
if(num==i){//去掉元素个数为0的环，剩下的元素个数
vis[num]=true;
count--;
}
ha[num]=i;
}
//剩下的环除了包含元素0的环，其他环的交换次数=环自身元素个数+1
for(i=;i<n;i++){
if(!vis[i]){
DFS(i,i);
count++;
}
}
if(ha[]!=){//如果0不单独成环，说明有元素个数>1的环包含0，则这个环在34行时多加了2，这里减去
count-=;
}
printf("%d\n",count);
return ;
}