题目描述

N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A swap consists of choosing any two people, then they stand up and switch seats.

The people and seats are represented by an integer from 0 to 2N-1, the couples are numbered in order, the first couple being (0, 1), the second couple being (2, 3), and so on with the last couple being (2N-2, 2N-1).

The couples’ initial seating is given by row[i] being the value of the person who is initially sitting in the i-th seat.

Example 1:

Input: row = [0, 2, 1, 3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3, 2, 0, 1]
Output: 0
Explanation: All couples are already seated side by side.

Note:

1. len(row) is even and in the range of [4, 60].
2. row is guaranteed to be a permutation of 0...len(row)-1.

题意：N对情侣坐在连续排列的2N 个座位上，想要牵到对方的手。 计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。 一次交换可选择任意两人，让他们站起来交换座位。人和座位用 0 到2N-1 的整数表示，情侣们按顺序编号，第一对是(0, 1)，第二对是(2, 3)，以此类推，最后一对是(2N-2, 2N-1)。这些情侣的初始座位row[i] 是由最初始坐在第i个座位上的人决定的。

算法1

(并查集)

我们设想一下加入有两对情侣互相坐错了位置，我们至多只需要换一次。
如果三对情侣相互坐错了位置，A1+B2,B1+C2,C1+A2。他们三个之间形成了一个环，我们只需要交换两次。
如果四队情侣相互坐错了位置，即这四对情侣不与其他情侣坐在一起，A1+B2,B1+C2,C1+D2,D1+A2.他们四个之间形成了一个环，他们只需要交换三次并且不用和其他情侣交换，就可以将这四对情侣交换好，
以此类推，其实就是假设k对情侣形成一个环状的错误链，我们只需要交换k - 1次就可以将这k对情侣的位置排好。
所以问题转化成N对情侣中，有几个这样的错误环。
我们可以使用并查集来处理，每次遍历相邻的两个位置，如果他们本来就是情侣，他们处于大小为1的错误环中，只需要交换0次。如果不是情侣，说明他们呢两对处在同一个错误环中，我们将他们合并（union），将所有的错坐情侣合并和后，答案就是情侣对 - 环个数。
这也说明，最差的情况就是所有N对情侣都在一个环中，这时候我们需要N - 1调换。
最好情况每对情侣已经坐好了，已经有N个大小为1的环，这时候我们需要N - N次调换。

C++ 代码

class Solution {
public:
    vector<int> fa,size;
    int getfa(int x)
    {
        if(x != fa[x]) fa[x] = getfa(fa[x]);
        return fa[x];
    }
    void uni(int x,int y )
    {
        int fx = getfa(x),fy = getfa(y);
        if(fx != fy)
        {
            if(size[fx] < size[fy])
            {
                fa[fx] = fy;
                size[fy] += size[fx];
            }else
            {
                fa[fy] = fx;
                size[fx] += size[fy];
            }
        }
    }
    int minSwapsCouples(vector<int>& row) {
        int n = row.size(),m = n / 2,res = 0,circle = 0;
        fa = vector<int>(m,0),size = vector<int>(m,1);
        for(int i = 0 ; i < m ; i ++) fa[i] = i;
        for(int i = 0 ; i < n ; i += 2)
            uni(row[i] / 2,row[i + 1] / 2);
        for(int i = 0; i < m ; i ++)
            if(i == getfa(i))
                circle ++;
        return m - circle;
    }
};