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: 1Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

Input: row = [3, 2, 0, 1]Output: 0Explanation: 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个座位，想让每一对情侣都能够牵手，也就是挨着坐。每次能交换任意两个人的座位，求最少需要换多少次座位。

解法1：cyclic swapping

解法2: Union Find

Java: 1

public int minSwapsCouples(int[] row) {    int res = 0, N = row.length;        int[] ptn = new int[N];        int[] pos = new int[N];        for (int i = 0; i < N; i++) {        ptn[i] = (i % 2 == 0 ? i + 1 : i - 1);        pos[row[i]] = i;    }        for (int i = 0; i < N; i++) {        for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {	    swap(row, i, j);	    swap(pos, row[i], row[j]);	    res++;	}    }        return res;}private void swap(int[] arr, int i, int j) {    int t = arr[i];    arr[i] = arr[j];    arr[j] = t;}

Java: 2

class Solution {    private class UF {        private int[] parents;        public int count;        UF(int n) {            parents = new int[n];            for (int i = 0; i < n; i++) {                parents[i] = i;            }            count = n;        }                private int find(int i) {            if (parents[i] == i) {                return i;            }            parents[i] = find(parents[i]);            return parents[i];        }                public void union(int i, int j) {            int a = find(i);            int b = find(j);            if (a != b) {                parents[a] = b;                count--;            }        }    }    public int minSwapsCouples(int[] row) {        int N = row.length/ 2;        UF uf = new UF(N);        for (int i = 0; i < N; i++) {            int a = row[2*i];            int b = row[2*i + 1];            uf.union(a/2, b/2);        }        return N - uf.count;    }}　

Python:

# Time:  O(n)# Space: O(n)class Solution(object):    def minSwapsCouples(self, row):        """        :type row: List[int]        :rtype: int        """        N = len(row)//2        couples = [[] for _ in xrange(N)]        for seat, num in enumerate(row):            couples[num//2].append(seat//2)        adj = [[] for _ in xrange(N)]        for couch1, couch2 in couples:            adj[couch1].append(couch2)            adj[couch2].append(couch1)        result = 0        for couch in xrange(N):            if not adj[couch]: continue            couch1, couch2 = couch, adj[couch].pop()            while couch2 != couch:                result += 1                adj[couch2].remove(couch1)                couch1, couch2 = couch2, adj[couch2].pop()        return result  # also equals to N - (# of cycles)　　

C++:

int minSwapsCouples(vector
     
      & row) {    int res = 0, N = row.size();            vector
      
        ptn(N, 0);    vector
       
         pos(N, 0);            for (int i = 0; i < N; i++) {        ptn[i] = (i % 2 == 0 ? i + 1 : i - 1);        pos[row[i]] = i;    }        for (int i = 0; i < N; i++) {        for (int j = ptn[pos[ptn[row[i]]]]; i != j; j = ptn[pos[ptn[row[i]]]]) {	    swap(row[i], row[j]);            swap(pos[row[i]], pos[row[j]]);	    res++;	}    }            return res;}