并查集的实现（朴素版）

         这是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++算法基础专栏文章    下一篇-并查集的实现（维护并查集大小版版）

---

每周一更新一篇文章，内容一般是自己总结的经验或是在其他网站上整理的优质内容

点个赞，关注一下呗~