一、前言
并查集，是 2022 新增考点，下面关于并查集的内容是根据王道讲解所总结的笔记（选择题和大题都有可能考）。
备注：并查集，在2022王道《数据结构》里有讲解，在第164页。
建议：最好结合第164页的图来理解下方的代码。
二、并查集
1、并查集：顺序存储，每一个集合组织成一棵树，采用 “ 双亲表示法 ”。
2、上代码
（1）基本内容
// 并查集的结构定义
#define SIZE 100
int UFset[SIZE]; // 集合元素数组（双亲指针数组）// 初始化（s[] 即为并查集）
void Initial(int s[]){for(int i = 0; i < SIZE; i++){s[i] = -1;}
}// Find操作：在s[] 中查找并返回包含元素 x 的树的根
// 最坏时间复杂度：O(n) （即结点排列形似成竖直状的单链表）
int Find(int s[], int x){while(s[x] >= 0) x = s[x]; // 循环寻找 x 的根return x; // 根的s[] < 0
}// Union操作：求两个不相交子集合的并集
// 时间复杂度：O(1)
void Union(int s[], int Root1, int Root2){if(Root1 == Root2) return; // 要求 Root1 和 Root2 是不同的，且表示字集合的名字s[Root2] = Root1; // 将 Root2 连接到另一根 Root1 下面
}（2）Find 操作（压缩路径） 和 Union 操作（小树并入大树）的优化
// Find操作的优化：
// 压缩路径（先找到根结点，再将查找路径上所有结点都挂到根结点下）
int Find(int s[], int x){int root = x;while(s[root] >= 0) root = s[root]; // 循环找到根while(x != root){ // 压缩路径int t = x; // t 指向 x 的父结点s[x] = root; // x 直接挂到根结点下x = t; // 继续使 x 的父结点也挂到根结点下}return root;
}// Union操作的优化：小树并入大树
void Union(int s[], int Root1, int Root2){if(Root1 == Root2) return;if(Root2 > Root1){ // Root2 结点数更少s[Root1] += s[Root2]; //累加结点总数s[Root2] = Root1; // 小树合并到大树}else{ // Root1 结点数更少s[Root2] += s[Root1]; //累加结点总数s[Root1] = Root2; // 小树合并到大树}
}（3）并查集的应用（3个，前2个重点掌握）
① 判断图的连通分量数; ② 判断图是否有环; ③ Kruskal算法;
举例：
上代码：
// 并查集的应用（3个）// 1. 判断图的连通分量数
// （1）用邻接矩阵 g[5][5] 表示无向图的边
int ComponentCount(int g[5][5]){int s[5];for(int k = 0; k < 5; k++){s[k] = -1; // 初始化并查集}// 遍历各条边（无向图，遍历上三角部分即可）for(int i = 0; i < 5; i++){for(int j = i + 1; j < 5; j++){if(g[i][j] > 0){ // 结点 i, j 之间有边int iRoot = Find(s, i); // 通过并查集找到 i 所属集合int jRoot = Find(s, j); // 通过并查集找到 j 所属集合if(iRoot != jRoot) Union(s, iRoot, jRoot); // i, j 并入同一集合}}}// 统计有几个连通分量int count = 0;for(int i = 0; i < 5; i++){if(s[i] < 0) count++;}return count; // count = 1, 说明是连通图；count > 1, 说明不是连通图，有count个连通分量；
}// （2）用邻接表表示无向图的边// 2. 判断图是否有环
// 用邻接矩阵 g[5][5] 表示无向图的边
int ComponentCount(int g[5][5]){int s[5];for(int k = 0; k < 5; k++){s[k] = -1; // 初始化并查集}// 遍历各条边（无向图，遍历上三角部分即可）for(int i = 0; i < 5; i++){for(int j = i + 1; j < 5; j++){if(g[i][j] > 0){ // 结点 i, j 之间有边int iRoot = Find(s, i); // 通过并查集找到 i 所属集合int jRoot = Find(s, j); // 通过并查集找到 j 所属集合if(iRoot != jRoot) Union(s, iRoot, jRoot); // i, j 并入同一集合else{ // i, j 原本就在同一个集合，即原本就连通return 1; //在一个连通子图中，但凡再多一条边，必有环。}}}}return 0; // 图中没有环
}
// 3. Kruskal算法
// 总的时间复杂度 ，总共执行e轮，每轮判断两个顶点是否属于同一个集合。
备注：关于Kruskal算法，想要进一步了解的可以看“ kruskal算法（克鲁斯卡尔算法）详解 ”
kruskal算法（克鲁斯卡尔算法）详解 (biancheng.net)