[LeetCode] Couples Holding Hands

这道题要求最少需要的swap的次数，最开始的想法是BFS求最短路径即可。但是复杂度太高。之后考虑了DP，但没有办法切分成独立的子问题。最后还考虑了binary search，虽然我们知道答案的范围一定是在[0,n]，n为couples的数量，但是给定交换数k，我们没有很效率的方法可以验证k次swap是否能让couple全部配对。
以上尝试失败之后，我们再次回到题目的本身。我们可以把每两个slot看做一个大的节点，我们要做的就是，让每一个大节点中包含一对夫妻。我们可以观察到，如果我们把每一对夫妻连线，那么我们可以建立起连接起节点的edge，每个node有两条边，并且整个图就是一个或者多个环。那五对夫妻为例，用编号0到4表示，如图所示(图片来自leetcode解答)：

这个例子只形成了一个环，当然还可以形成更多的换，这取决于我们的初始状态。对于每一环，我们只需要在环内部，每次固定一个元素x1，并且沿着路径swap回来x1的配偶，就可以让他们全部配对，当然我们不需要回到起始位置，起始位置被swap的元素会一直沿着路径进入最后一个节点，也就是起始节点的另一个相邻节点。也就是说对于size为n的环，我们只需要n - 1就次swap可以让这个环上的节点全部valid。那么这道题就变成了给定图，找环的数量和大小。我们只需要DFS即可。

时间复杂度和空间复杂度都为O(n)，代码如下：