【问题求解I-HW6.C】万圣节的新娘
题意概述
给定 $n$ 个数对，保证 $1\cdots n$ 中的每个数恰好出现两次。每次操作可以任意交换两个数的位置。问至少多少次交换可以使得每对数都相同。
约束条件：$n\leq 10^6$。
这道题颇有思维难度，需要仔细观察并发现问题的性质。发现问题的性质不能靠双眼瞪着屏幕——动起手来，画几个样例手算出解法，很多时候解决问题的灵感就是从手算得出的。
我们首先可以确定一件事：答案的上限是 $n-1$，因为每轮操作你总可以让某一个数对匹配起来。如果你手算尝试了一些样例，你一定会发现想要让交换次数最少，我们会格外喜欢这样的数对：
1 2
2 1
因为我们只要让上面的 2 和下面的 1 交换，我们就可以一下子得到两个匹配的数对，这看起来非常赚。但不是什么时候都能有“动一次成两对”这么赚的事情，你很快会发现有的时候格局可能是这样的：
1 2
2 3
3 5
5 8
8 1
通过观察你可以发现：这样的 5 个数对你只要将前 4 个搞定，最后一个也会随之搞定，且你无法给出比 4 次交换更好的方案。
你是否觉得上面的 5 个数对像是 1, 2, 3, 5, 8 五个数构成的环？事实上，稍加思索你便能发现 $n$ 个数对其实就是由这样的若干个互不影响的“环”组成的。每个环形如
a1 a2
a2 a3
...
an-1 an
an a1
这样一个长度为 $n$ 的环，我们需要 $n-1$ 次操作将其全部搞定，每有一个“环”，我们就可以“节省”一次操作。因此，设 $n$ 个数对共由 $m$ 个环构成，那么最小的操作次数就是 $n-m$。
判断环的个数相对简单，你并不一定需要使用“并查集”这样高级的数据结构——事实上搜索已经足够完成任务了，这部分的细节留给大家自行思考。