并查集的实现（朴素版）
这是C++算法基础-数据结构专栏的第二十九篇文章，专栏详情请见此处。
由于作者即将参加CSP，所以到比赛结束前将不再发表文章！
引入
并查集是一种可以快速合并查找集合的一种数据结构，这次我们将通过三道题来详细讲解并查集（朴素版、维护并查集大小版和维护到祖宗节点距离版），而这次我们要学习朴素版的并查集。
下面我们就来讲并查集的实现（朴素版）。
定义
并查集是一种用于管理元素所属集合的数据结构，实现为一个森林，其中每棵树表示一个集合，树中的节点表示对应集合中的元素。
过程
例题：合并集合
题目大意：起初一共有
个数，每个数都各自在一个集合中。现在要进行
个操作，操作共两种：将两个数
所在的集合合并；询问两个数
操作：合并和查找
并查集，顾名思义，它就是支持两种基本操作的数据结构：并（合并）和查（查找）。它的原理就是用一个数组记录每个节点的祖宗节点，通过对这个数组的更新实现数据之间的联系。刚开始所有节点的根都是它本身。
首先，我们需要实现一个函数find()，用来寻找一个节点的根，方法很简单，只需不断递归，一直访问现在节点的祖宗节点，直到访问到根节点（即该节点的是本身）。
首先是第一个操作：合并。合并时只需要将其中一个节点的根的赋值为另一个节点的根。
第二个操作：查找。查找两个节点是否在同一棵树上，仅仅判断两个节点的find()是否相同即可。
Q：为什么不直接比较
呢？
A：因为在合并时，若有两棵树进行合并，可能中途的节点的
优化：路径压缩和按秩合并
接下来我们进行优化，在实现find()函数的过程中，很明显，一路上经过的点都在这个集合中，为了加快后续查询，我们可以将其直接连到根上。这一优化我们称为路径压缩。这个优化大大的降低了时间复杂度。
有时题目需要保留原有的树的结构，这时我们就不能采用路径压缩了。合并时，我们可以在每棵树的根上记录树的层数，把层数小的树合并到层数大的树，很明显，这样做可以减少合并后树的层数，这叫做按秩合并。
由于路径压缩的优化程度比按秩合并要大，所以我们一般仅仅采用路径压缩就足够了。课程中也只是提到了按秩合并，并没有讲解，所以在代码中我们也不采用按秩合并。
代码
下面给出朴素版并查集的实现代码：
int p[N];
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
for(int i=1;i<=n;i++) p[i]=i;
p[find(a)]=find(b);代码解释
第一行是存储每个节点的祖宗节点的数组；find()函数的作用是寻找根节点；for循环中的内容的作用是初始化；最后一行的作用是合并。
上一篇-Trie树之最大异或对问题 C++算法基础专栏文章 下一篇-并查集的实现（维护并查集大小版版）
每周一更新一篇文章，内容一般是自己总结的经验或是在其他网站上整理的优质内容
点个赞，关注一下呗~
原文地址：https://blog.csdn.net/wyuchen123/article/details/142469076
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！