概述

并查集是用来处理一些不相交集合的合并和查询问题，开始时每个元素都是一个集合，然后在处理中会依据一些规则来进行集合的合并。在逻辑上，并查集是由很多树组成的森林，而在实际的代码中，我们往往使用数组来储存，数组的下标表示树的节点，下标对应的元素表示该节点的父节点。另外，我们定义根节点的父节点是它自己。并查集的操作有：

查询某个节点的根节点
合并两个集合

代码实现

初始化

首先定义一个 vector 来表示并查集。在初始化时，我们将其中每个元素设为其对应下标的值。

vector<int> vec;
//初始化代码
vec.resize(n, 0);//n代表元素的数量
for (int i = 0; i < n; i++) vec[i] = i;

查询

查询指查询给定节点的根节点。若两个节点的根节点相同，则表示这两个节点在同一个集合里。在代码中，如果某个节点不是根节点（表现为元素与其对应的下标不相等），则递归地查找其父节点的根节点，并将其父节点直接修改为根节点以减少下次查找所需要的时间（称为“路径压缩”）。

int find(int root) {
    if (vec[root] != root) vec[root] = find(vec[root]);
    return vec[root];
}

合并

合并指将给定两个节点所在的集合合并为一个集合。在代码中通过将其中一个集合的根节点的父节点设置成另一个节点的根节点，这样两个集合就有了共同的根节点，即合并为同一个集合了。

void union_root(int r1, int r2) {
    vec[find(r1)] = vec[find(r2)];
    return;
}

例题

LeetCode 765. 情侣牵手

n 对情侣坐在连续排列的 2n 个座位上，想要牵到对方的手。

人和座位由一个整数数组 row 表示，其中 row[i] 是坐在第 i 个座位上的人的 ID。情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2n-2, 2n-1)。

返回 最少交换座位的次数，以便每对情侣可以并肩坐在一起。 每次交换可选择任意两人，让他们站起来交换座位。

示例 1：

1
2
3

输入: row = [0,2,1,3]
输出: 1
解释: 只需要交换row[1]和row[2]的位置即可。

示例 2:

1
2
3

输入: row = [3,2,0,1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。

题解

通过观察我们可以发现：

如果有 2 对情侣彼此坐错了位置，则需要进行 1 次交换。
如果有 3 对情侣彼此坐错了位置，则需要进行 2 次交换。
如果有 4 对情侣彼此坐错了位置，则需要进行 3 次交换。
如果有 n 对情侣彼此坐错了位置，则需要进行 n-1 次交换。

那么我们可以采用并查集的数据结构，将彼此坐错的情侣放进同一个集合，记并查集森林中有 cnt 棵树，共有 n 对情侣，那么需要交换的次数就是 n-cnt 。

代码

class Solution {
private:
    vector<int> vec;
    int find(int root) {
        if (vec[root] != root) vec[root] = find(vec[root]);
        return vec[root];
    }
    void union_root(int r1, int r2) {
        vec[find(r1)] = vec[find(r2)];
        return;
    }
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size(); int m = n / 2;
        vec.resize(m, 0);
        for (int i = 0; i < m; i++) vec[i] = i;
        for (int i = 1; i <= m; i++) {
            union_root(row[2 * i - 2] / 2, row[2 * i - 1] / 2);
        }
        int cnt = 0;
        for (int i = 0; i < m; i++) {
            if (find(i) == i) cnt++;
        }
        return m - cnt;
    }
};

在代码中，我们用某个人的 ID 除以 2 来表示ta和ta对象共同的 情侣ID，然后把实际上挨着坐的人都 union 起来。如果他们本来就是情侣，则最终他们所在集合就只会有一个元素，表示这个集合中的人不需要交换。 union 到最后，我们得到的并查集中每个集合的情侣都坐混了，需要互相发生交换；而不同集合中的情侣之间则不需要发生交换。

有的没的

速通《空洞骑士》

这游戏很简单的，两个多小时就通关了(狗头)。

环己三烯的冬眠舱

并查集

概述