UVA11330 Andy's Shoes —— 置换分解

题目链接：https://vjudge.net/problem/UVA-11330

题意：

给出n双鞋子，鞋子按左右左右地摆放，但“左右”是否为一对鞋子是不确定的。问：至少交换多少次鞋子，才能把每双鞋子都放好。

题解：

1.可知，对于“左”鞋子是不需要调整的，只需调整“右”鞋子，使得它们都各自放到了相应“左”鞋子的右边。

2.因此，可以把右鞋子的摆放情况看成是置换。然后对置换进行分解，求出循环节cnt，则只需交换n-cnt次。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <cmath>

 #include <queue>

 #include <stack>

 #include <map>

 #include <string>

 #include <set>

 using namespace std;

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int MOD = 1e9+;

 const int MAXN = 2e4+;

 bool vis[MAXN];

 int A[MAXN];

 int main()

 {

     int T, kase = , n;

     scanf("%d", &T);

     while(T--)

     {

         scanf("%d",&n);

         memset(vis, true, sizeof(vis));

         for(int i = ; i<=n; i++)

         {

             int l, r;

             scanf("%d%d", &l,&r);

             A[l] = r;

             vis[l] = false;

         }

         int cnt = ;

         for(int i = ; i<MAXN; i++)

         {

             if(!vis[i])

             {

                 int j = i;

                 cnt++;

                 do

                 {

                     vis[j] = true;

                     j = A[j];

                 }while(j!=i);

             }

         }

         printf("%d\n", n-cnt);

     }

 }