本篇内容介绍了“C++并查集有哪些常用操作”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！
并查集 是一种树型的数据结构,用于处理一些不相加集合的合并和查询问题。在使用中常常以森林来表示。 并查集也是用来维护集合的,和前面学习的set不同之处在于,并查集能很方便地同时维护很多集合。如果用set来维护会非常的麻烦。并查集的核心思想是记录每个结点的父亲结点是哪个结点。
并查集是一种多叉树，用于处理不相交的集合的合并与查询问题（判断）。
通俗理解：在日常生活中，我们会因为某个人是自己的朋友，哪怕是朋友的朋友也是有朋友，会给予通融、 偏袒。而并查集的基本概念，就是判断某两个集合是否是“朋友”关系，并让两个集合成为“朋友”
初始化：每个结点单独作为一个集合
查询：求元素所在的集合的代表元素，即根结点
合并：将两个元素所在的集合，合并为一个集合
合并之前，应先判断两个元素是否属于同一集合，用上面的“查询”来实现
初始化:初始的时候每个结点各自为一个集合,father[i]表示结点 i 的父亲结点,如果 father[i]=i,我们认为这个结点是当前集合根结点（开始时每个节点根节点是他自己）。
void init() {
for (int i = 1; i <= n; ++i) {
father[i] = i;
}
}查找:查找结点所在集合的根结点,结点 x 的根结点必然也是其父亲结点的根结点（像是有递归的样子）。
int get(int x) {
if (father[x] == x) { // x 结点就是根结点
return x;
}
return get(father[x]); // 如果该节点不是根节点，继续寻找父结点的根结点
}合并:将两个元素所在的集合合并在一起,通常来说,合并之前先判断两个元素是否属于同一集合。
void hebing(int x, int y) {
x = find(x);
y = find(y);
if (x != y) { // 不在同一个集合
father[y] = x;//将根节点合并
}
}上面三个操作是并查集常用的操作
前面的并查集的复杂度实际上在有些极端情况会很慢。比如树的结构正好是一条链，那么最坏情况下，每次查询的复杂度达到了O(n) 。这并不是我们期望的结果。路径压缩的思想是，我们只关心每个结点的父结点，而并不太关心树的真正的结构（递归查找相当浪费时间）如下：
当想去访问6的根节点时，要访问5的根节点，想去访问5的根节点，又要去访问4的根节点..........以此类推，此时并查集退化为线性。
这样我们在一次查询的时候，可以把查询路径上的所有结点的father[i]都赋值成为根结点。只需要在我们之前的查询函数上面进行很小的改动
int findf(int k)
{ if(f[k] == k)
return k;
return f[k] = findf(f[k]); //后来更新的点的根节点直接为最开始的点，一步找到总根节点。
}“C++并查集有哪些常用操作”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
