poj 1674

随便看到的一个题

给出 n 个数，问最小的交换次数可以让这 n 个数变成升序排列的

这个一开始还以为dp呢，可是想了好长时间也不知道怎么dp，原来是找给的n个数里的环的问题，比如说样例 2

2 3 5 4 1 这里面有两个环 {2,3,5,1},{4}，2应该在的位置是 3，3应该在的位置是 5，5应该在的位置是 1，然后1 就到 2 了，所以就是一个环，然后最小的交换次数就是 n - 环数

View Code

 1 const int N = 10010;
 2 struct node
 3 {
 4     int x;
 5     int id;
 6 }a[N];
 7 bool vis[N];
 8 int main()
 9 {
10     int i,j;
11     int t,n;
12     //freopen("data.txt","r",stdin);
13     scanf("%d",&t);
14     while(t--)
15     {
16         _clr(vis,0);
17         scanf("%d",&n);
18         int flag = 0;
19         int sum;
20         for(i = 1; i <= n; i++)
21         {
22             scanf("%d",&a[i].x);
23             if(i != a[i].x) flag = 1;
24             a[i].id = i;
25         }
26         if(!flag)
27         {
28             printf("0\n");
29             continue;
30         }
31         sum = 0;
32         for(i = 1; i <= n; i++)
33         {
34             flag = 0;
35             int temp = a[i].x;
36             if(!vis[i]) sum ++;
37             if(i != temp && !vis[i])
38             {
39                 //sum ++;
40                 vis[temp] = 1;
41                 while(i != temp)
42                 {
43                    flag = 1;
44                    temp = a[temp].x;
45                    vis[temp] = 1;
46                 }
47             }
48         }
49         printf("%d\n",n - sum);
50     }
51     return 0;
52 }