hdu6489 2018 黑龙江省大学生程序设计竞赛j题

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath> 
using namespace std;
const int N = 1e6+10;
int a[N],vis[N];  //vis数组记录每个数是否找过他应该在的位置 
int main()
{
	int t;
	scanf("%d",&t);
	while(t--){
		memset(vis,0,sizeof(vis)); 
		int ans = 0;
		int n,i;
		scanf("%d",&n);
		for(i = 1; i <= n; i++){
			scanf("%d",&a[i]);
		}
		for(i = 1; i <= n; i++){
			int temp = a[i],x = 0;
			while(!vis[temp]){  //temp 还没找过其应在的位置 
				vis[temp] = 1;  //标记temo已经找过 
				temp = a[temp];  //用temp应在的位置上的数覆盖temp，如果其在应在的位置那么继续while循环直接跳出然后不用做交换 
				x++;
			}
			if(x > 0){
				ans += x-1;  //遍历每一组情况下应该对x减一才能得到正确的交换次数 
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}