5.11.1 并查集

并查集是一种树形的数据结构，顾名思义，它用于处理一些不交集的合并及查询问题。 它支持两种操作：

• 查找（Find）：确定某个元素处于哪个子集；
• 合并（Union）：将两个子集合并成一个集合。

一个功能完全的类模板（参考力扣）：

并查集类模板

#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
    int n;                    // 初始节点数
    int setN;                // 集合数量
    vector<int> parent;        // 祖宗节点
    vector<int> size;        // 合并优化操作使用，记录集合大小
    // 通过构造函数初始化数组
    UnionFind(int _n): n(_n), setN(_n), parent(_n), size(_n, 1) {
        for (int i=0; i<_n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (size[x] > size[y]) {
            swap(x, y);
        }
        parent[x] = y;
        size[y] += size[x];
        --setN;
    }
    bool isCon(int x, int y) {
        return find(x) == find(y);
    }
};
int n, m;
int main() {
    cin >> n >> m;
    UnionFind* uf = new UnionFind(n);
    // 合并两个元素所在集合
    cin >> x >> y;
    uf->unite(x, y);
    // 询问两个元素是否在一个集合中
    cin >> x >> y;
    cout << (uf->isCon(x, y) ? "Yes" : "No") << endl;
    return 0;
}

例题 1：蓝桥 合根植物【第八届】【决赛】

这是一道模板题，你可以在读懂模板的基础上，先行自己尝试。

参考代码

#include <bits/stdc++.h>
using namespace std;
class UnionFind {
public:
    int n;
    int setN;
    vector<int> parent;
    vector<int> size;
    UnionFind(int _n): n(_n), setN(_n), parent(_n), size(_n, 1) {
        for (int i=0; i<_n; ++i) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (size[x] > size[y]) {
            swap(x, y);
        }
        parent[x] = y;
        size[y] += size[x];
        --setN;
    }
    bool isCon(int x, int y) {
        return find(x) == find(y);
    }
};
int n, m;
int k;
int main() {
    cin >> n >> m >> k;
    UnionFind* uf = new UnionFind(n * m);
    while (k--) {
        int x, y;
        cin >> x >> y;
        uf->unite(x - 1, y - 1);    // 本题序号从 1 起
    }
    cout << uf->setN << endl;
    return 0;
}

并查集由于属于一种树形结构，通常不需要做所有的优化，它的复杂度解释起来比较复杂，你可以理解为每次操作接近。熟练之后，你可以不必默写整个模板，使用数组模拟，有简便写法：

int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x) {
    return p[x] == x ? x : p[x] = find(p[x]);
}
// 初始化，假定节点编号是1~n
for (int i=1; i<=n; ++i) {
    p[i] = i;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);

这样一来，你可以灵活调整题目给定编号从 1 起的状况，减少代码量。你可以自己想一想怎么实现模板的查询当前不连通集合数量 setN 的操作。

推荐阅读：算法学习笔记(1) : 并查集