文档章节

Union Find-并查集

梦想游戏人
 梦想游戏人
发布于 2017/07/29 11:27
字数 537
阅读 11
收藏 0
点赞 0
评论 0

并查集是在各个不相交集合中查找某元素存在否,可以接近常数级查找例如,图的连通性,最近公共祖先等问题。一般用森林 数组实现。

一般有2个操作,查找(find)和合并(union)

查找:从集合中查找元素x是否存在。

合并:如果2个集合不想交则可以合并操作,一般方法是高度低的合并到高度高的。

初始化每个元素都可以是一个单独的集合,然后不断引入关系来合并他们

问题引入:

若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

简单地看是2个元素xy在这个庞大的关系网络中是否有是亲戚关系,每个成员都可以看做是一个元素,常规的图论做法深度搜索 代价比较大。

并查集很适合这种情况下的查找判断

可以通过hash来简化这个过程,元素按照1234567 来区分,对应数组0123456下标,存储的内容就是父节点,表达的意思是和其父节点是亲戚关系。

初始化,数组初始存储值是其本身,表示没有关系

初始数组0123456,其中456为第二个集合

输入ab,数组变为0023456,1的父节点是0表示他们是亲戚关系

输入bd,数组变为0021456,3的父节点是1他们是亲戚关系

输入ac,数组变为0001456,2的父节点是0

第一组集合输入完毕,对于第二组集合

输入ef,数组变为0001446

输入fg,数组变为0001445

上述输入是关于数组的合并操作,对应代码

© 著作权归作者所有

共有 人打赏支持
梦想游戏人
粉丝 34
博文 402
码字总数 115594
作品 0
成都
SQL集合运算:差集、交集、并集

1、差集( except ) select a from t_a except select a from t_b -- 也可写作: select a from ta where a not in (select a from tb) -- 多个字段时: select a,b from t_a except select ......

颖辉小居 ⋅ 2016/11/04 ⋅ 0

SQL集合运算:差集、交集、并集

1、差集( except ) select a from t_a except select a from t_b -- 也可写作: select a from ta where a not in (select a from tb) -- 多个字段时: select a,b from t_a except select ......

赵帅A ⋅ 2016/04/27 ⋅ 0

PLSQL一些实用语法介绍

并行查询:取并集,也就是所有的数据 (select deptno from emp) union (select deptno from dept); 交集查询: 取两个表的交集,结果即属于A又属于B; (select deptno from emp) intersect (...

yangfei86 ⋅ 2014/05/13 ⋅ 0

Union-Find Set 并查集

v2-b87b6b4929022f7581ccd6e58df4a1fc_r.png ![TOC] 并查集操作的复杂度是log n。是一个衰减非常快的函数,即使n 很大,log n的结果也接近一个常数,不会超过5。 其实并查集顾名思义就是有“...

陈黎栋知心话 ⋅ 2017/12/15 ⋅ 0

使用explain来分析MySQL 查询性能

为了在MySQL中写出高效的SQL脚本,我们的SQL必须时时都要用来检查其执行计划,时时调整。 的使用方法为: 比如下面这条SQL 在MySQL执行完以后如下所示: 下面说一下这些列都代表什么: sele...

古城痴人 ⋅ 2015/08/19 ⋅ 0

LeetCode 721. Accounts Merge

原题 Given a list accounts, each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing......

likewind1993 ⋅ 2017/11/17 ⋅ 0

Oracle 提高查询性能(基础)

#1,选择最有效的表名顺序 Oracle解析器总是按照从右至左的顺序处理FROM后面的表,因此FROM最右边的表将会被当做驱动表优先处理,当存在多个表关联时,应当使用记录少的表当做驱动表。如果关...

王大叔爱编程 ⋅ 2014/09/15 ⋅ 0

ZOJ 3261 Connections in Galaxy War 【并查集 + 离线逆向处理】好题!!

传送门 // 题意: 给定一幅(n, m) 图, 每个点有点权, 然后有一些询问 destroy a b 表示摧毁a与b直接相连的边, 保证删除之前这两个点之间一定有边 query a 询问a可以到达的点中点权最大的且比a...

anxdada ⋅ 03/02 ⋅ 0

算法导论——最小生成树:Kruskal算法(利用了并查集)

package org.loda.graph; import org.loda.structure.MinQ;import org.loda.structure.Queue;import org.loda.util.In; /*** @ClassName: KruskalMST @Description:Kruskal最小生成树算法 @a......

jonathan_loda ⋅ 2015/05/26 ⋅ 0

来自圣经的十大算法

1 Union-Find(并查集):它借用树结构来处理集合的合并操作和查询操作 2 KMP 3 BFPRT 4 Quicksort 5 Floyd-Warshall algorithm:求得所有最短路径的方法 6 Gentry’s Fully Homomorphic Enc...

nothingfinal ⋅ 2012/02/11 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

apollo配置中心的学习笔记

公司现在配置文件太多了,导致配置文件修改起来还是非常麻烦的。在boss(业务运营支撑系统)中,配置文件是存放在jar包的,通过应用jar包来引用配置文件(区分不同环境)。这种方式虽然能够满足...

miaojiangmin ⋅ 1分钟前 ⋅ 0

Jena增删改查AP

插入、更新数据 public static void insert(){ String query = "PREFIX book: <http://www.book.com/jinyong/> \n" + " INSERT DATA \n" + ......

Vincent-Duan ⋅ 1分钟前 ⋅ 0

springMVC之与json数据交互方法

因为我也要返回json数据。所以需要这个注解@ResponseBody,把Java对象转换成json字符串 注意: 1、@RequestBody不能省,因为前台发过来的数据是json数据,得用这个注解去解析该怎么接收这些数...

颖伙虫 ⋅ 5分钟前 ⋅ 0

用实例域代替序号(31)

1、许多枚举天生就与一个单独的int 值相关联 ordinal 方法,返回枚举常量在类型中的数字位置 下述,枚举修改很不方便,不好维护 永远不要根据枚举的序数导出与他相关联的值 而是将他保存在一...

职业搬砖20年 ⋅ 7分钟前 ⋅ 0

并发编程---ConcurrentHashMap源码解析

ConcurrentHashMap是java中为了解决HashMap不能支持高并发而设计的新的实现。 ConcurrentHashMap的类结构 public class ConcurrentHashMap<K,V> extends AbstractMap<K,V> implements C......

千古一梦888 ⋅ 10分钟前 ⋅ 0

微服务 WildFly Swarm 简介

我们将看到的最后一个Java微服务框架是一个相对较新的场景,它利用了 JBoss WildFly 应用服务器中已试过且受信任的 JavaEE 功能。WildFly Swarm 是 WildFly 应用服务器的一个完整的拆下来的组...

woshixin ⋅ 15分钟前 ⋅ 0

android apk 瘦身

头条APK瘦身之路 随着版本迭代,功能增加安装包体积也会慢慢增大。 今日头条576版本APK达到了25M,通过一系列的优化,到目前的607版本为12M。本文主要是介绍头条APK瘦身中用到的一些方法。 ...

GoldenVein ⋅ 19分钟前 ⋅ 1

mac机器学习开发环境部署及helloworld

一、下载并安装Anaconda2.7 https://repo.anaconda.com/archive/Anaconda2-5.2.0-MacOSX-x86_64.pkg 路径:/Users/shijun/anaconda2 二、运行Anaconda Navigator -> Environments -> base(ro......

八戒八戒八戒 ⋅ 30分钟前 ⋅ 0

关于日常开发的经验总结(Java),持续更新中

常量尽量使用枚举来表示,这样表现力会很强,因为枚举比一个常量类要有更多的扩展性 方法的入参和出参尽量不要使用Map,因为Map会让调用者感到迷惑,他不知道你里面装的什么,面向对象的开发...

小99 ⋅ 30分钟前 ⋅ 0

IDEA创建SpringMVC+Mybatis+Maven项目

视频如下(加载有点慢请见谅,服务器不太好): 视频

影狼 ⋅ 30分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部