本文共 1235 字，大约阅读时间需要 4 分钟。
和UVa11077的分析很类似。
我们固定左脚的鞋子不动，然后将右脚的鞋子看做一个置换分解。
对于一个长度为l的循环节，要交换到正确位置至少要交换l-1次。
1 #include 2 #include 3 #include 4 using namespace std; 5 6 bool vis[10000 + 10]; 7 8 int main() 9 {10 //freopen("in.txt", "r", stdin);11 12 int T;13 scanf("%d", &T);14 while(T--)15 {16 int n, a, b;17 map m;18 scanf("%d", &n);19 for(int i = 0; i < n; i++)20 {21 scanf("%d%d", &a, &b);22 m[a] = b;23 }24 int ans = 0;25 map ::iterator It;26 memset(vis, false, sizeof(vis));27 for(It = m.begin(); It != m.end(); It++)28 {29 int i = It->first;30 if(!vis[i])31 {32 int cnt = 0;33 int j = i;34 do35 {36 cnt++;37 vis[j] = true;38 j = m[j];39 }while(j != i);40 ans += cnt - 1;41 }42 }43 printf("%d\n", ans);44 }45 46 return 0;47 }
转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4373121.html
