【LightOJ】1166 - Old Sorting（置换群）

点击打开题目

1166 - Old Sorting

Given an array containing a permutation of 1 to n, you have to find the minimum number of swaps to sort the array in ascending order. A swap means, you can exchange any two elements of the array.

For example, let n = 4, and the array be 4 2 3 1, then you can sort it in ascending order in just 1 swaps (by swapping 4 and 1).

Input

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains two lines, the first line contains an integer n (1 ≤ n ≤ 100). The next line contains n integers separated by spaces. You may assume that the array will always contain a permutation of 1 to n.

Output

For each case, print the case number and the minimum number of swaps required to sort the array in ascending order.

置换群的经典应用，求出每个群的元素个数，减一就是这个群交换的次数。最后求个和就行了。

代码如下：

#include <cstdio>
#include <cstring>
#define CLR(a) memset(a,0,sizeof(a)) 
int main()
{
	int n;
	int u;
	int num[111];
	bool used[111];
	int ans;
	scanf ("%d",&u);
	int Case = 1;
	while (u--)
	{
		scanf ("%d",&n);
		for (int i = 1 ; i <=  n ; i++)
			scanf ("%d",&num[i]);
		printf ("Case %d: ",Case++);
		ans = 0;
		CLR(used);
		for (int i = 1 ; i <= n ; i++)
		{
			if (!used[i])
			{
				int t = num[i];
				used[i] = true;
				int d = 1;
				while (t != i)
				{
					used[t] = true;
					t = num[t];
					d++;
				}
				ans += d - 1;
			}
		}
		printf ("%d\n",ans);
	}
	return 0;
}