并查集快速查找

雨点打透心脏的1/2处 2024-03-16 23:18 22阅读 0赞

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。

查询元素所在的集合编号，直接返回 **id** 数组值，**O(1)** 的时间复杂度。

> ...  
> private int find(int p) \{  
> assert p >= 0 && p < count;  
> return id\[p\];  
> \}  
> ...

合并元素 **p** 和元素 **q** 所属的集合， 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并，这个过程是 **O(n)** 复杂度。

> ...  
> public void unionElements(int p, int q) \{  
> int pID = find(p);  
> int qID = find(q);  
> if (pID == qID)  
> return;  
> for (int i = 0; i < count; i++)  
> if (id\[i\] == pID)  
> id\[i\] = qID;  
> \}  
> ...

#### Java 实例代码 ####

### UnionFind1.java 文件代码： ###

> package runoob.union;  
>   
> /\*\*  
> \* 第一版union-Find  
> \*/  
> public class UnionFind1 \{  
> // 我们的第一版Union-Find本质就是一个数组  
> private int\[\] id;  
> // 数据个数  
> private int count;  
>   
> public UnionFind1(int n) \{  
> count = n;  
> id = new int\[n\];  
> // 初始化, 每一个id\[i\]指向自己, 没有合并的元素  
> for (int i = 0; i < n; i++)  
> id\[i\] = i;  
> \}  
>   
> // 查找过程, 查找元素p所对应的集合编号  
> private int find(int p) \{  
> assert p >= 0 && p < count;  
> return id\[p\];  
> \}  
>   
> // 查看元素p和元素q是否所属一个集合  
> // O(1)复杂度  
> public boolean isConnected(int p, int q) \{  
> return find(p) == find(q);  
> \}  
>   
> // 合并元素p和元素q所属的集合  
> // O(n) 复杂度  
> public void unionElements(int p, int q) \{  
>   
> int pID = find(p);  
> int qID = find(q);  
>   
> if (pID == qID)  
> return;  
>   
> // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并  
> for (int i = 0; i < count; i++)  
> if (id\[i\] == pID)  
> id\[i\] = qID;  
> \}  
> \}

发表评论取消回复

表情：

评论列表（有 0 条评论，22人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集快速合并

对于一组数据，并查集主要支持两个动作： union(p,q) - 将 p 和 q 两个元素连接起来。 find(p) - 查询 p 元素在哪个集合中。 is

骑猪看日落/ 2024年03月16日 23:18/ 0 赞/ 44 阅读

相关并查集快速查找

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。 > ... > pri

雨点打透心脏的1/2处/ 2024年03月16日 23:18/ 0 赞/ 23 阅读

相关并查集快速查找

本小节基于上一小节并查集的结构介绍基础操作，查询和合并和判断是否连接。查询元素所在的集合编号，直接返回 id 数组值，O(1) 的时间复杂度。 > ... > pri

落日映苍穹つ/ 2024年03月16日 22:49/ 0 赞/ 35 阅读

相关并查集快速合并（Java 实例代码）

目录并查集快速合并 Java 实例代码 UnionFind2.java 文件代码： -------------------- 并查集快速合并对于一组数据，并

拼搏现实的明天。/ 2023年10月14日 21:07/ 0 赞/ 42 阅读

相关并查集快速查找（Java 实例代码）

目录并查集快速查找 Java 实例代码 UnionFind1.java 文件代码： -------------------- 并查集快速查找本小节基于上一小

梦里梦外;/ 2023年10月14日 21:06/ 0 赞/ 44 阅读

相关并查集初始化查找合并路径压缩

/ 并查集 / include <stdio.h> int father[7]; //初始化 void init() {

- 日理万妓/ 2023年07月04日 11:13/ 0 赞/ 20 阅读

相关并查集

这个文章是几年前水acm的时候转的, 当时也不知道作者是谁, 要是有人知道的话说一下吧并查集是我暑假从高手那里学到的一招，觉得真是太精妙的设计了。以前我无法解决的

港控/mmm°/ 2022年06月13日 14:13/ 0 赞/ 301 阅读

相关并查集

> 题目 > 某学校近期要组织全校同学出去参加某项活动，由于人数众多，学校决定让同学们自行组队，以小组为单位进行活动。假设学校一共n个同学，每个同学有一个唯一的数字作为标签

Myth丶恋晨/ 2022年06月08日 09:24/ 0 赞/ 308 阅读

相关并查集

森林: 森林是由若干棵互不相交的树组成,两棵树分别独立,没有交集 ![20181112082744488.png][] 并查集: 并查集的结构和森林十分相似,是

Love The Way You Lie/ 2022年04月17日 02:27/ 0 赞/ 367 阅读

相关并查集

来看一个实例，[杭电1232畅通工程][1232] 首先在地图上给你若干个城镇，这些城镇都可以看作点，然后告诉你哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性

我就是我/ 2022年03月29日 10:58/ 0 赞/ 370 阅读