文章作者:Slyar 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。
等价关系与等价类
从数学上看,等价类是一个对象(或成员)的集合,在此集合中的所有对象应满足等价关系。若用符号"≡"表示集合上的等价关系,那么对于该集合中的任意对象x,y, z,下列性质成立:
1、自反性:x ≡ x
2、对称性:若 x ≡ y 则 y ≡ x
3、传递性:若 x ≡ y 且 y ≡ z 则 x ≡ z
因此,等价关系是集合上的一个自反、对称、传递的关系。
通过金属线连接起来的电器的连通性,就是一种等价关系。这种关系显然具有自反性,因为任何一个器件都是与自身连通的;如果a 电连通b,那么b一定也电连通a,因此这种关系具有对称性; 若a连通到b,并且b连通到c,那么a连通到c 。
并查集
并查集的一般用途就是用来维护某种具有自反、对称、传递性质的关系的等价类。并查集一般以树形结构存储,多棵树构成一个森林,每棵树构成一个集合,树中的每个节点就是该集合的元素,找一个代表元素作为该树(集合)的祖先。
并查集支持以下三种操作:
1、Make_Set(x) 把每一个元素初始化为一个集合
初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身。
2、Find_Set(x) 查找一个元素所在的集合
查找一个元素所在的集合,只要找到这个元素所在集合的祖先即可。判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。
3、Union(x,y) 合并x,y所在的两个集合
合并两个不相交集合操作很简单:首先设置一个数组Father[x],表示x的"父亲"的编号。那么,合并两个不相交集合的方法就是,找到其中一个集合的祖先,将另外一个集合的祖先指向它。
并查集的优化
1、Find_Set(x)时 路径压缩
寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?
答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回归"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了。
2、Union(x,y)时 按秩合并
即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。
主要代码实现
1
2
3
4
|
/* father[x]表示x的父节点 */
int father[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
|
1
2
3
4
5
6
|
/* 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
}
|
1
2
3
4
5
6
7
8
9
|
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/* 按秩合并x,y所在的集合 */
void Union(int x, int y)
{
x = Find_Set(x);
y = Find_Set(y);
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
|
相关题目
并查集的基础应用:
POJ 1611 The Suspects C语言版
POJ 2524 Ubiquitous Religions C语言版
POJ 1182 食物链 C语言版
最小生成树Kruskal算法并查集应用:
POJ 1258 Agri-Net C语言版 Kruskal
POJ 1251 Jungle Roads C++版 Kruskal
POJ 1861 Network C语言版 Kruskal
分享到:
相关推荐
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复...
数据结构 并查集 查询 快速 实用 ACM
并查集 第12章 并查集
并查集模板并查集模板并查集模板并查集模板并查集模板并查集模板
深入理解并查集算法,细致讲解,专业老师,一步到位 。
学习并查集的好东东,需要的看看吧,ACM之路
并查集讲义,清楚明白地讲解并查集原理及优化
并查集详解
并查集,acm,并查集的入门课件,主要使用与ACM学习
C++版并查集的课件,定义,并查集的精髓代码以及路径压缩的内容
C++整理\并查集\并查集初步.ppt 并查集初步
在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一...即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果,只能用并查集来描述。
并查集的简介,用法,以及一些例子
算法与数据结构:并查集实现的方法,以及ACM并查集的一些例子
并查集原理和代码实现。或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否亲戚应该是可行的,但如果两个人的最近公共祖先与他们...
关于并查集的几道经典题目,希望对大家有所帮助
并查集的一些基础知识讲解,详细的PPT,希望对搜索者有帮助!
最经典并查集详细讲解, 最经典并查集详细讲解。
使用C++实现了并查集的建立,合并和查找功能,并附简单的测试用例。