情侣牵手

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

1. 贪心+哈希

对于按顺序编号并配对的问题，可以考虑用图的思维来思考
把人两两归到一起，看做一个节点，一对情侣关系看做一条边，每个节点存在两条边，原数组可以抽象成不同节点连成的多个环
不过我们可以先用贪心的思想来做，每次使得一对情侣坐到一起，其实从图的角度来看，就是将环中的两个节点中合并并释放掉了一对情侣

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        int count = 0;
        map<int,int> m;//对应值的位置，后面还要用于交换位置
        for(int i=0;i<n;i++)
            m[row[i]] = i;
        for(int i=0;i<n;i=i+2){
            int first = row[i];
            int couple = first^1;
            int index = m[couple];
            if(index/2==i/2) continue;//位于同一块
            //否则要将first 的老婆位置与i+1对换
            m[row[i+1]] = index;
            swap(row[i+1],row[index]);
            count++;
        }
        return count;
    }
};

2. 图+哈希

节点数n/2 - 环的个数等于最终结果，即需要释放情侣的次数

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        int count = 0;
        map<int,int> m;//对应值的位置
        vector<bool> visit(n/2);
        for(int i=0;i<n;i++)
            m[row[i]] = i;
        for(int i=0;i<n;i=i+2){
            if(visit[i/2]) continue;
            int index = i;
            while(!visit[index/2]){ //遍历当前环的循环,下一个没访问过
                visit[index/2] = true;
                int nei_index = index^1;//得到邻居下标
                int neibor = row[nei_index];
                int couple = neibor^1;//得到邻居的老婆
                index = m[couple];//转移到邻居老婆对应的节点
            }
            count++;//环个数加一
        }
        return n/2-count;
    }
};

3. 并查集

跟方法二思路差不多，只不过用模板,合并更为方便
把相邻两数所在的节点合并

class Solution {
public:
    vector<int> p;
    void union_(int a, int b) {
        p[find(a)] = p[find(b)];
    }
    int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        int m = n/2;
        int count = 0;
        p.resize(m);//初始节点个数
        for(int i =0;i<m;i++)//初始化节点集合
            p[i] = i;
        for(int i=0;i<n;i=i+2)
            union_(row[i]/2,row[i+1]/2);//合并两节点
        for(int i=0;i<m;i++)
            if(find(i)==i) count++;//集合个数，即环个数
        return m-count;
    }
};