并查集-理论知识

比眉伴天荒 2022-01-20 02:35 177阅读 0赞

### 概念 ###

并查集（union & find）是一种树形数据结构，用于处理不交集的查找和合并。

find：确定元素属于哪个子集；判断两个元素是否属于同一个子集。

union：合并两个子集。

拆分复杂，通常不支持也不常用拆分。

### 作用 ###

帮派识别

### 数据结构实现和代码 ###

数组

public class QuickUnionUF {
    
        private int[] roots;
    
        public QuickUnionUF(int N) {
            roots = new int[N];
            for (int i = 0; i < N; i++) {
                roots[i] = i;
            }
        }
    }
    复制代码

roots\[i\] = i 表示节点上级为自己

伪代码如下

function MakeSet(x)
            x.root := x
            
        function Find(x)
            if x.root := x
                return x
            else
                return Find(x.root)
                
        function Union(x, y)
            xRoot := Find(x)
            yRoot := Find(y)
            xRoot.root = yRoot
    复制代码

### 两种优化方式 ###

1.  合并的时候减少树的深度（rank），把深度低的子集merge到深度高的子集上

function MakeSet(x)
            x.root := x
            x.rank := 0
            
        function Union(x, y)
            xRoot := Find(x)
            yRoot := Find(y)
            if yRoot.rank > xRoot.rank
                xRoot.root := yRoot
            else if yRoot.rank < xRoot.rank
                yRoot.root := xRoot
            else
                xRoot.root := yRoot
                yRoot.rank := yRoot.rank + 1
    复制代码

1.  路径压缩，直接找到最大的老大赋值为直接上级

public int Find(int x) {
            int root = x;
            while (root != roots[root]) root = roots[root];
            
            while (x != roots[x]) {
                int tmp = roots[x];roots[x] = root;x = tmp;
            }
            return root;
        }
    复制代码

发表评论取消回复

表情：

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

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

相关阅读

相关并查集理论及常见面试题

并查集理论及常见面试题 1 并查集理论 1）有若干个样本a、b、c、d…类型假设都是V 2）在并查集中一开始认为每个样本都在单独的集合里 3）用户可以在任何

冷不防/ 2024年04月08日 12:56/ 0 赞/ 83 阅读

相关并查集 Ⅱ

\[poj 1611\] ([http://poj.org/problem?id=1611][http_poj.org_problem_id_1611]) 题目描述： T

古城微笑少年丶/ 2022年08月03日 14:35/ 0 赞/ 259 阅读

相关并查集

并查集JAVA版框架并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作： \--查询元素a和元素b是否属于同一组

落日映苍穹つ/ 2022年06月16日 12:44/ 0 赞/ 296 阅读

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集

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

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

相关并查集-理论知识

概念并查集（union & find）是一种树形数据结构，用于处理不交集的查找和合并。 find：确定元素属于哪个子集；判断两个元素是否属于同一个子集。 union

比眉伴天荒/ 2022年01月20日 02:35/ 0 赞/ 178 阅读

相关并查集

一、算法解释用于解决一些有N个元素的集合应用问题。 1、将每个元素初始化为自身单独成为一个集合。用p\[i\]的值表示该元素所在集合。 ![这里写图片描述][S

桃扇骨/ 2021年09月14日 02:56/ 0 赞/ 453 阅读

相关并查集

并查集的作用就是快速判断两个元素是否在同一个集合中，快速将两个集合合并基本模板 include <iostream> include <a

比眉伴天荒/ 2021年06月22日 15:37/ 0 赞/ 545 阅读