c++初级并查集知识点总结

并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题。

有一个联合- 查找算法定义了两个用于此数据结构的操作：

  • Find ：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union：将两个子集合并成同一个集合。

并查集主要运用在合并元素以及查询两个元素是否在同一集合的问题，在信息学竞赛中广泛涉及

初始化：

一开始，每一个元素都是一个集合，打个比方，每个人所在的 " 家族 " 只有他一个人。我们还需要一个 f 数组，里面存的是他的 “父亲” 的编号，初始值为 f[1]=1,f[2]=2……f[n]=n，如图

2、find函数：find（a）是用来查找a的“祖先”的，例如，我们要查找 a 的祖先，就要去找 a 的父亲的父亲……，直到有个人 b ，他的父亲就是他自己，那么 b 就是 a 的祖先代码如下：int find (int x){    if(f[x] == x) return x;//如果x的父亲就是他自己，则x为a的祖先 else return find (f[x]);//否则a的祖先 就是a的父亲的祖先}int x=find(a);find函数：find（a）是用来查找a的“祖先”的，例如，我们要查找 a 的祖先，就要去找 a 的父亲的父亲……，直到有个人 b ，他的父亲就是他自己，那么 b 就是 a 的祖先代码如下：int find (int x){    if(f[x] == x) return x;//如果x的父亲就是他自己，则x为a的祖先 else return find (f[x]);//否则a的祖先 就是a的父亲的祖先}int x=find(a);

union函数：

union(a,b) 就是合并 a,b 这两个人所在的家族，只需要把 a的祖先的父亲 指向 b的祖先

如何合并？我们设 u=find(a),v=find(b) , 只要将 u,v 其中一个人的父亲编号指向另外一个人就行了，例如 f[u]=v

代码如下：

void Union (int a,int b)//因为union是c++的保留字，所以只好大写u

{

  int u= find(a), v= find(b);//寻找a，b的祖先

  f[u]=v;//合并家族

}

Union (a,b);

在合并的时候还有一个注意点：为什么不能直接把 a 的父亲指向 b ？因为这样并不能合并完全，a 的父亲， a 的父亲的父亲……，都不能合并到 b 的家族里（想一想，为什么？），如图

5、查询两个元素是否在同一集合里：查询 a,b 是否在同一集合里，就是看他们的祖先是否相等，若相等则在同一集合里，否则就不在代码如下：if( find(a) == find(b) ) cout<<"Y\n"; //如果祖先相等就输出“Y”else cout<<"N\n"; //否则输出“N”查询两个元素是否在同一集合里：查询 a,b 是否在同一集合里，就是看他们的祖先是否相等，若相等则在同一集合里，否则就不在代码如下：if( find(a) == find(b) ) cout<<"Y\n"; //如果祖先相等就输出“Y”else cout<<"N\n"; //否则输出“N”

例题：

至此，你应该对并查集有了初步的了解，是时候上例题了

题目描述

如题，现在有一个并查集，你需要完成合并和查询操作。

输入输出格式

输入格式：

第一行包含两个整数N、M，表示共有N个元素和M个操作。

接下来M行，每行包含三个整数Zi、Xi、Yi

当Zi=1时，将Xi与Yi所在的集合合并

当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N

输出格式：

如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为Y或者N

其实，这道题目就是把上面几个步骤综合在一起，代码如下

并查集的路径压缩

路径压缩，顾名思义，就是将本来要很多步完成的事情压缩成一步

因为我们每次 find(a) 都要消耗 O (a 的层数 ) 的时间，如果数据构造成一条链，则每次 find 都需要 O(n) 的时间，这是我们不希望看到的

所以，我们可以把 f 数组的性质改变一下 f[a] 指向的编号变为 a 的祖先

代码该怎么写呢？我们只需要在 find 函数里把

return find (f[x]);

变成

return f[x]=find(f[x]);

就可以了

这样每一次 find 都会使路径上的每个 f[x] 指向 x 的祖先，每一次 find 也就只需要 1 步就行了（除非被合并过，那也只需要 2 步），这就是路径压缩的实质

赞 (0)

相关推荐

  • C++并查集亲戚(Relations)算法实例

    本文实例讲述了C++并查集亲戚(Relations)算法.分享给大家供大家参考.具体分析如下: 题目: 亲戚(Relations) 或许你并不知道,你的某个朋友是你的亲戚.他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子.如果能得到完整的家谱,判断两个人是否亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及.在这种情况下,最好的帮手就是计算机. 为了将问题简化,你将得到一些亲戚关系的信息,如同Marry和Tom是亲戚,Tom和B en是

  • c++初级并查集知识点总结

    并查集是一种树型的数据结构,用于处理一些不交集的合并及查询问题. 有一个联合- 查找算法定义了两个用于此数据结构的操作: Find :确定元素属于哪一个子集.它可以被用来确定两个元素是否属于同一子集. Union:将两个子集合并成同一个集合. 并查集主要运用在合并元素以及查询两个元素是否在同一集合的问题,在信息学竞赛中广泛涉及 初始化: 一开始,每一个元素都是一个集合,打个比方,每个人所在的 " 家族 " 只有他一个人.我们还需要一个 f 数组,里面存的是他的 "父亲&quo

  • C#并查集(union-find)算法详解

    C#并查集(union-find)算法详解

    目录 算法的主题思想: 1. 动态连通性 2. 定义问题 3. quick-find算法实现 算法分析 4. quick-union算法实现 森林表示 算法分析 5.加权 quick-union 算法实现 算法分析 6.最优算法 - 路径压缩 算法的主题思想: 1.优秀的算法因为能够解决实际问题而变得更为重要: 2.高效算法的代码也可以很简单: 3.理解某个实现的性能特点是一个挑战: 4.在解决同一个问题的多种算法之间进行选择时,科学方法是一种重要的工具: 5.迭代式改进能够让算法的效率越来越高

  • java编程实现并查集的路径压缩代码详解

    java编程实现并查集的路径压缩代码详解

    首先看两张路径压缩的图片: 并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题.一些常见的用途有求连通子图.求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等. 使用并查集时,首先会存在一组不相交的动态集合 S={S 1 ,S 2 ,⋯,S k } ,一般都会使用一个整数表示集合中的一个元素. 每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表.每个集合中具体包含

  • python实现一个简单的并查集的示例代码

    并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题.常常在使用中以森林来表示. 并查集有三种基本操作,获得根节点,判断两节点是否连通,以及将两不连通的节点相连(相当于将两节点各自的集合合并) 用UnionFind类来表示一个并查集,在构造函数中,初始化一个数组parent,parent[i]表示的含义为,索引为i的节点,它的直接父节点为parent[i].初始化时各个节点都不相连,因此初始化parent[i]=i,让自己成为自己的父节点,从而实现各节点不互连. def __ini

  • c语言数据结构之并查集 总结

    并查集(Union-Find Set): 一种用于管理分组的数据结构.它具备两个操作:(1)查询元素a和元素b是否为同一组 (2) 将元素a和b合并为同一组. 注意:并查集不能将在同一组的元素拆分为两组. 并查集的实现: 用树来实现. 使用树形结构来表示以后,每一组都对应一棵树,然而我们就可以将这个问题转化为树的问题了,我们看两个元素是否为一组我们只要看这两个元素的根是否一致.显然,使用树形结构将问题简单化了.合并时是我们只需要将一组的根与另一组的根相连即可. 并查集的核心在于,一棵树的所有节点

  • 数据结构与算法之并查集(不相交集合)

    认识并查集 对于并查集(不相交集合),很多人会感到很陌生,没听过或者不是特别了解.实际上并查集是一种挺高效的数据结构.实现简单,只是所有元素统一遵从一个规律所以让办事情的效率高效起来. 对于定意义,百科上这么定义的: 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受:即使在

  • Java使用HashMap实现并查集

    并查集的定义: 并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中.这一类问题近几年来反复出现在信息学的国际国内赛题中,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述. 并查集是一种树型的数

  • c++并查集优化（基于size和rank）

    基于size的优化是指:当我们在指定由谁连接谁的时候,size数组维护的是当前集合中元素的个数,让数据少的指向数据多的集合中 基于rank的优化是指:当我们在指定由谁连接谁的时候,rank数组维护的是当前集合中树的高度,让高度低的集合指向高度高的集合 运行时间是差不多的: 基于size的代码: UnionFind3.h #ifndef UNION_FIND3_H_ #define UNION_FIND3_H_ #include<iostream> #include<cassert>

  • C++利用map实现并查集

    并查集(Union-Find)是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题. 并查集存在两个操作(1.Union 联合 2.finddeputy 查找代表结点) 和一个需要解答的问题( issameset 是否 在一个集合中,或者说是否有同一个代表结点). 利用map实现主要通过两个map的对象 ,一个map<data,data>类型的fathermap,关键字为子结点,值为其父结点(父结点不一定就是代表结点),当我们需要查找两个两个元素是否在一个

随机推荐