[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)，代码如下：

	class Solution {
	public:
	int minSwapsCouples(vector<int>& row) {
	int n = row.size() / 2, res = 0;
	unordered_map<int, int> map;
	unordered_set<int> path, visited;
	for(int i = 0; i < 2 * n; ++i)map[row[i]] = i;
	for(int i = 0; i < 2 * n; ++i)
	if(visited.find(i / 2) == visited.end())
	res += findCycle(row, map, path, visited, i) - 1;
	return res;
	}
	private:
	int findCycle(vector<int>& row, unordered_map<int, int>& map, unordered_set<int>& path, unordered_set<int>& visited, int to)
	{
	int slot = to / 2, next = map[row[to ^ 1] ^ 1];
	if(path.find(slot) != path.end())return path.size();
	if(visited.find(slot) != visited.end())return 0;
	visited.insert(slot);
	path.insert(slot);
	int size = findCycle(row, map, path, visited, next);
	path.erase(slot);
	return size;
	}
	};

view raw Couples Holding Hands.cpp hosted with ❤ by GitHub