本篇是并查集专题我在写洛谷的时候经常遇到需要利用并查集解决的算法题例如无向图判环无向图连通分量个数等等每当我遇到这类题都想不到合适的解题方法到但是看了题解之后发现都是利用了并查集这个数据结构话不多说上干货1、引出原理讲解双亲表示法接下来要学习到的并查集本质上就是用双亲表示法实现的森林。因此我们先认识⼀下双亲表示法在学习树这个数据结构的时讲到树的存储方式有很多种孩⼦表示法双亲表示法、孩子双亲表示法以及孩子兄弟表示法等对⼀棵树而言除了根节点外其余每个结点⼀定有且仅有⼀个双亲双亲表示法就是根据这个特点存储树的也就是把每个结点的双亲存下来因此我们可以采用数组来存储每个结点的⽗亲结点的编号这就实现了双亲表示法注意在实现并查集的时我们⼀般让根节点自己指向⾃⼰。因此上述存储就变成2、并查集的概念查询操作查找元素x属于哪一个集合一般在每个集合中选取一个元素作为代表查询的是这个集合的代表元素即查找到最终的父亲合并操作将元素x所在的集合与元素y所在的集合合并成一个集合(注意合并的是两个元素所在的集合而不是这两个元素)判断操作判断x和y是否在同一个集合并查集是⼀种用于维护元素所属集合的数据结构实现为⼀个森林其中每棵树表⽰⼀个集合树中的节点表示对应集合中的元素根节点来代表整个集合3、并查集的实现(1)初始化初始状态下所有元素单独成为一个集合即fa数组指向自己即可const int N 1e6 10; int n; int fa[N]; // 双亲表⽰法所需的数组 for (int i 1; i n; i) { fa[i] i; }(2)查询操作此处直接展示路径优化版本路径压缩在查询时把被查询的节点到根节点的路径上的所有节点的⽗节点设置为根节点从而减小树的深度也就是说在向上查询的同时把在路径上的每个节点都直接连接到根上以后查询时就能直接查询到根节点int find(int x) { //1.if版本 if (fa[x] x) return fa[x]; else fa[x] find(fa[x]); //2.三目版本 return fa[x] x ? x : fa[x] find(fa[x]); }(3)合并操作将元素x所在的集合与元素y所在的集合合并成⼀个集合让元素x所在树的根节点的父节点指向元素y的父节点//合并-名字不能取union void un(int x, int y) { int fx find(x); int fy find(y); if(fx!fy) fa[fx] fy; }(4)判断操作判断这两个元素的父亲节点是否相同//判断 bool issame(int x, int y) { return find(x) find(y); }4、例题展示---Watering the Fields S以以前写的代码展开详细描述与解释,并附上题目const int N 2010, M 2e6 10; int n, c; int x[N], y[N]; int m; struct node { int u, v, w; }e[M]; int fa[N]; bool cmp(node x, node y) { return x.w y.w; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } int calc(int i, int j) { return (x[i] - x[j]) * (x[i] - x[j]) (y[i] - y[j]) * (y[i] - y[j]); } int main() { cin n c; for (int i 1; i n; i) cin x[i] y[i]; //建图 for (int i 1; i n; i) { for (int j i 1; j n; j) { int t calc(i, j); if (t c) { m; e[m] { i,j,t }; } } } for (int i 1; i n; i) fa[i] i; sort(e 1, e 1 m, cmp); int ret 0, cnt 0; for (int i 1; i m; i) { int u e[i].u, v e[i].v, w e[i].w; int fu find(u), fv find(v); if (fu fv) continue; cnt; ret w; fa[fu] fv; if (cnt n - 1) break; } if (cnt n - 1) cout ret endl; else cout -1 endl; return 0; }这是一道在洛谷上写的题目所以使用全局的变量更加方便根据输入要求我直接把数组设置的足够大那么就不用考虑越界的问题实现本题的逻辑主要在于并查集n有n组数据c代价最小不小于cnode结构体u与v代表边w代表权重cmp排序逻辑Kruskal算法要求(最小生成树)需要把权重从小到大排序find函数并查集的查找逻辑以O(1)的时间复杂度找到父节点calc函数计算边长的平方即权重不要根号以防浮点数错误第二个for循环中这是建图操作把所有符合条件的权重都存入到e[N]数组中之后使用(e[m]{i,j,t}这是c语法记住就好不用纠结)ret存最终值cnt存边的个数第三个for循环就是遍历边生成构建最小生成树先将当前位置的数据拿出来使用find函数找到对应的父节点如若父节点相同就continue掉因为如果已经连在一起了在统计这个边的话就会形成环造成后续错误如若父节点不相同那么就统计当前边个数并加上当前权重到ret中如若最终的cntn-1那么就代表找了最终答案如若找不到n-1条边那么就证明没有正确答案返回-1