并查集在引入之前，需要先教会学生集合的概念。

集合

集合是数学中的一个基本概念，它是由一些确定的、彼此不同的对象所组成的整体。集合有两个特点：

• 集合中的元素是互不相同的。
• 集合中的元素没有顺序之分。比如集合 {1, 2, 3} 和 {3, 2, 1} 是同一个集合。

生活中的集合有很多，比如：班级，家庭成员，朋友等等。所以，学生还是比较容易理解的。

并查集

并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。

并查集支持两种操作：

• 查询（Find）：查询某个元素所属集合（查询对应的树的根节点），这可以用于判断两个元素是否属于同一集合
• 合并（Merge）：合并两个元素所属集合（合并对应的树）

在教学并查集的时候，画示意图可以很好地让学生理解并查集的操作。

并查集的初始化

我们用数组来表示并查集，用数组的值表示当前结点的父亲。如下图所示：

所以，初始化的代码如下：

1
2
3
4
5
6
7
8

#define MAXN 1010

int p[MAXN], n;
void init() {
    for (int i = 0; i <= n ; ++i) {
        p[i] = i;
    }
}

并查集的查询操作

并查集在查询时，从初始结点开始，判断自己是不是根结点。根结点的特征是自己是自己的父亲。如果自己不是根结点，则继续递归往上找。示例代码如下：

1
2
3
4

int find(int a) {
    if (p[a] == a) return a;
    return find(p[a]);
}

我们在这儿，也顺便引入路径压缩的优化，告诉学生在返回值的时候，如果更新结点，就可以把下图中的长路径“拍扁”，使得下次查询的时候速度更快。

那么如何更新呢？只需要在上面的代码基础上做一点点改动，如下：

1
2
3
4

int find(int a) {
    if (p[a] == a) return a;
    return p[a] = find(p[a]); // 在返回值之前，更新结点值
}

以上代码可以简化成一行：return p[a]==a ? a : (p[a] = find(p[a]));。但是教学的时候，还是展开让学生理解清楚后，再提供简化的写法比较好。

并查集的合并操作

合并的时候，像上图那样，我们把一个结点的根结点的父亲，指向另外一个根结点即可。

1
2
3
4
5

void merge(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    p[pa] = pb;
}

以上代码可以简化成一行：p[find(a)]=find(b);。但是教学的时候，还是展开让学生理解清楚后，再提供简化的写法比较好。

判断并查集中集合的个数

因为有一个根结点，就代表有一个集合，所以我们可以数根结点的个数来得到集合的个数。

根结点的特点是：它的父结点就是自己。相关代码如下：

1
2
3
4
5
6

int cnt = 0;
for (int i = 1; i <=n; ++i) {
    if (p[i] == i) {
        cnt++;
    }
}

并查集的练习题

完成以上的基础教学，就可以练习了。并查集的考查主要就是两个：

• 判断两点是否联通
• 计算连通块（集合）的个数

以下是基础的练习题目。

题目	说明
P1551 亲戚	基础题
P1536 村村通	基础题
P1892 团伙	提高题，需要用反集
剩余内容已隐藏 查看完整文章以阅读更多 查看完整文章