[数据结构#1] 并查集 | FindRoot | Union | 优化 | 应用

目录

1. 并查集原理

问题背景

名称与编号映射

数据结构设计

2. 并查集基本操作

(1) 初始化

(2) 查询根节点 (FindRoot)

(3) 合并集合 (Union)

(4) 集合操作总结

并查集优化

(1) 路径压缩

(2) 按秩合并

3. 并查集的应用

(1) 统计省份数量

(2) 判断等式方程是否成立

并查集是一种用于处理 元素分组和集合操作 的数据结构，主要功能是支持以下两种操作：

  1. 合并：将两个集合合并成一个集合。
  2. 查询：判断某个元素属于哪个集合。

并查集实际上是由多棵 互不相交的树 组成的森林，以下是详细的整理内容。

1. 并查集原理

问题背景

在一些问题中，需要将 n  个不同的元素划分为若干个互不相交的集合，并支持以下操作：

  • 查询某个元素所属的集合。
  • 合并两个集合。

例如，某公司校招的 10 名学生，分别来自不同地区，起初各自独立。根据他们的交流情况，可以将其分为几个小团体。通过并查集，可以很好地表示这些分组关系，并实现高效的集合操作。

  • 首先先给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个数。(负号下文解释)

继续往下看，如何描述他们之间的关系呢？

西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。如何表示这三个集合呢？

很简单，把他们建立三颗树形结构。一个数据结构有多颗树不就是之前所说的森林了。如何建树呢？一个集体随便选取一个节点作根，剩下节点取做它的孩子。

那我们如何来表示这里的集合结构呢？

并查集是森林，森林是由多个树组成，这里用两层来表示这里的关系。

  1. 像堆类似，用数组下标表示关系
  2. 双亲表示法（存储双亲的下标）

仔细观察数组中内融化，可以得出以下结论：

  1. 数组的下标对应集合中元素的编号
  2. 数组中如果为负数，负号代表根，数字绝对值 代表该集合中元素个数
  3. 数组中如果为非负数，代表该元素双亲在数组中的下标

合并过程：

继续往下看，如何将已经有的集合合并呢？ 刚才都是独立的集合直接合并，现在是已经有集合怎么合并呢?

比如说在公司工作一段时间后，西安小分队中8号同学与成都小分队4号同学奇迹般的走到了一起，两个小圈子的学生相互介绍，最后成为了一个小圈子：怎么合并呢？

  • 不能直接合并，而是找到两个数的根，让根合并。


找根很简单，看自己位置保存的是不是负数，如果是负数自己就是根了，如果不是负数保存的就是双亲的下标了，就去看看双亲下标保存的是不是负数，不是负数还跳，直到找到双亲下标保存的值是负数，这个下标也就是根了。

把1下标的值加道0下标，然后1下标位置保存0下标。

通过以上例子可知，并查集一般可以解决一下问题：

  1. 查找元素属于哪个集合
    沿着数组表示树形关系以上一直找到根(即：树中中元素为负数的位置)
  2. 查看两个元素 是否属于同一个集合
    沿着数组表示的树形关系往上一直找到树的根，如果根相同表明在同一个集合，否则不在
  3. 将两个集 合归并成一个集合
    将两个集合中的元素合并
    将一个集合名称改成另一个集合的名称
  4. 集合的个数
    遍历数组，数组中元素 为负数的个数即为集合的个数。

下面就实现一下并查集~

名称与编号映射

  • 可能会有这样的问题，内部给他们编号，万一外面给的是10个人给的是名字，我怎么知道谁是那个编号呢？怎么解决？

借助vector，map建立对应映射关系！

  • vector：存储名称列表，通过下标快速找到名字。
  • map：建立名字到编号的映射关系。

代码示例：

template<class T>
class UnionFindSet
{
public:
UnionFindSet(const T* a, size_t sz)
{
    for (int i = 0; i < sz; ++i)
        {
            _a.push_back(a[i]);//将数组中元素添加到vector中
            _IndexMap[a[i]] = i;//将人映射到hash中
        }
}


private:
vector<T> _a;          //编号找人
map<T, int> _IndexMap; //人找编号
};

int main()
{
    string arr[] = { "张三","李四","王五","赵六" };
    UnionFindSet<string> ufs(arr, 4);
    return 0;
}
  • _a.push_back(a[i]);：这一行代码将数组 a 的第 i 个元素添加到成员变量 _a 向量的末尾。这里 a 是构造函数参数中的一个指针，指向传入的数组，而 a[i] 则是该数组中第 i 个位置的元素。
  • _IndexMap[a[i]] = i;：此行代码则是在建立一个映射关系。它使用成员变量 _IndexMap，这是一个从类型 T 映射到整数类型的关联容器（map）。这里它将数组 a 的第 i 个元素作为键，i 作为值插入到 _IndexMap 中。因此，以后当我们知道某个人的名字时，可以通过 _IndexMap 快速查找这个人在原始数组中的索引位置。

这样不管是给下标还是给名字都可以解决这里的问题。

数据结构设计

并查集通过一个数组表示关系：

  • 数组下标 表示集合中的元素编号。
  • 数组值 用于表示该元素的父节点或根节点的信息。
    • 负数：表示集合的根，绝对值为该集合中元素的个数。
    • 非负数：表示其父节点在数组中的下标。

双亲表示法：每个节点存储其父节点的位置，通过不断向上查找父节点，最终可以找到集合的根节点。

2. 并查集基本操作

(1) 初始化

  • 初始时，每个元素自成一个集合，数组值均为 -1，表示每个集合的大小为 1。
UnionFindSet(int sz)
    : _ufs(sz, -1) {}  // 初始化，大小为 sz，每个位置存储 -1

(2) 查询根节点 (FindRoot)

  • 找到某个元素所在集合的根节点。
  • 如果当前节点的父节点为负数，则该节点是根节点。
  • 路径压缩：为了提高查询效率，将查询路径上的所有节点直接连接到根节点。
int FindRoot(int x) {
    int root = x;
    // 向上查找根节点
    while (_ufs[root] >= 0) {
        root = _ufs[root];//利用上述讲到的特性原则，实现向上查找
    }

    // 路径压缩
    while (_ufs[x] >= 0) {
        int parent = _ufs[x];
        _ufs[x] = root;
        x = parent;
    }

    return root;
}

这里在补充说一点，并查集 路径压缩 的问题。比如集合是下面这个样子，要从9找到根需要跳很多层。影响找根的效率，能不能想到什么办法把路径压缩一下呢？

其实也很简单 ，反正都是在同一个集合，是不是直接可以考虑把下面的直接压到根的下面做根的孩子。这样就变成了一层。如果数据量很多层数很高压缩路径后这样很不错。

  • 一般在查找根的时候去压缩。
  • 查找谁就把它这一条路径压缩。
  • 找到根之后判断一下，如果它的父亲就是根就不用压缩，如果不是说明中间有间隔层，然后就可以把这条路径压缩。

比如是这个4，首先先把4变成2的孩子，然后将4的父亲1也去变成2的孩子，这条路径都可以变成2的孩子。

(3) 合并集合 (Union)

  • 并查集 除了路径压缩，还有一种提高效率的方式，比如两个集合 合并的时候
    • 小集合向大集合合并，以减少树的深度。
  • 实现步骤：
    • 找到两个集合的根节点。
    • 如果根节点相同，说明两个元素已在同一个集合中，无需合并。
    • 否则，将小集合的根指向大集合的根，并更新集合大小。
bool Union(int x1, int x2) {
    int root1 = FindRoot(x1);
    int root2 = FindRoot(x2);

    if (root1 == root2) return false;

    // 控制小集合向大集合合并
    if (abs(_ufs[root1]) < abs(_ufs[root2])) {
        swap(root1, root2);
    }

    _ufs[root1] += _ufs[root2];
    _ufs[root2] = root1;

    return true;
}

(4) 集合操作总结

  • 查找元素所属集合：找到其根节点。
  • 判断两个元素是否属于同一集合：检查它们的根节点是否相同。
  • 统计集合数量：统计数组中负数的个数，即为集合的数量。

并查集优化

(1) 路径压缩
  • 在查询根节点时，将路径上的节点直接连接到根节点，减少树的高度。
  • 优化后的查找复杂度接近 O(1) 。
(2) 按秩合并
  • 优先将元素较少的集合合并到元素较多的集合，进一步减少树的高度。
  • 实现方法：比较根节点的绝对值，选择小集合向大集合合并。

完整代码：

#pragma once

#include<iostream>
#include<vector>
#include<map>

using namespace std;

//template<class T>
//class UnionFindSet
//{
//public:
//	UnionFindSet(const T* a, size_t sz)
//	{
//		for (int i = 0; i < sz; ++i)
//		{
//			_a.push_back(a[i]);
//			_IndexMap[a[i]] = i;
//		}
//	}
//
//
//private:
//	vector<T> _a;          //编号找人
//	map<T, int> _IndexMap; //人找编号
//};


class UnionFindSet
{
public:
	UnionFindSet(int sz)
		:_ufs(sz,-1)// 初始时，将数组中元素全部设置为1
	{}


	bool Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		// x1已经与x2在同一个集合
		if (root1 == root2)
			return false;

		//控制数据量小的往大的集合合并
		if (abs(_ufs[root1]) < abs(_ufs[root2]))
		{
			swap(root1, root2);
		}

		// 将两个集合中元素合并
		_ufs[root1] += _ufs[root2];

		// 将其中一个集合名称改变成另外一个
		_ufs[root2] = root1;

		return true;
	}

	// 给一个元素的编号，找到该元素所在集合的名称
	int FindRoot(int x)
	{
		int root = x;
		while (_ufs[root] >= 0)// 如果数组中存储的是负数，找到，否则一直继续
		{
			root = _ufs[root];
		}

		//路径压缩
		while (_ufs[x] >= 0)
		{
			int parent = _ufs[x];
			_ufs[x] = root;
			x = parent;
		}

		return root;
	}

	bool IsSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	// 数组中负数的个数，即为集合的个数
	size_t SetSize()
	{
		size_t count = 0;
		for (auto e : _ufs)
		{
			if (e < 0) 
				++count;
		}
		return count;
	}

private:
	vector<int> _ufs;
};

3. 并查集的应用

(1) 统计省份数量

题目链接：[LCR 116. 省份数量]

  • 思路：
    • 使用并查集，将直接连接的城市合并到同一个集合。
    • 遍历矩阵，统计并查集中集合的数量。

代码实现：

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    vector<int> ufs(n, -1);

    auto Findroot = [&](int x) {
        while (ufs[x] >= 0) {
            x = ufs[x];
        }
        return x;
    };

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (isConnected[i][j] == 1) {
                int root1 = Findroot(i);
                int root2 = Findroot(j);
                if (root1 != root2) {
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }
    }

    return count_if(ufs.begin(), ufs.end(), [](int x) { return x < 0; });
}

(2) 判断等式方程是否成立

题目链接：[990. 等式方程的可满足性]

  • 思路：
    • 将所有“相等”的变量合并到同一个集合。
    • 遍历“不等”关系，若两个变量属于同一个集合，则矛盾。

代码实现：

bool equationsPossible(vector<string>& equations) {
    vector<int> ufs(26, -1);

    auto Findroot = [&](int x) {
        while (ufs[x] >= 0) {
            x = ufs[x];
        }
        return x;
    };

    // 合并“相等”关系
    for (auto& eq : equations) {
        if (eq[1] == '=') {
            int root1 = Findroot(eq[0] - 'a');
            int root2 = Findroot(eq[3] - 'a');
            if (root1 != root2) {
                ufs[root1] += ufs[root2];
                ufs[root2] = root1;
            }
        }
    }

    // 检查“不等”关系
    for (auto& eq : equations) {
        if (eq[1] == '!') {
            int root1 = Findroot(eq[0] - 'a');
            int root2 = Findroot(eq[3] - 'a');
            if (root1 == root2) return false;
        }
    }
    return true;
}

这是一道并查集的板子，==号我们可以认为两个字母之间存在一条边，先遍历一遍把所有 == 的字母进行连接，然后再次遍历看一下不相等的字母是否在一个连通分量上，那么主要就是怎么连接以及怎么去判断两个字母是否在同一个连通分量上，这就要用到并查集的知识。
这里推荐一篇博客，讲的挺好的，主要是路径压缩的时候优化了查找的时间。看完之后秒懂并查集。

并查集详解 ——图文解说,简单易懂(转)-CSDN博客

并查集 使用场景：两极性的集合划分

连接或不连接，相等或不相等 的判断 

并查集是一种高效的数据结构，支持快速的 合并 和 查询 操作，并在路径压缩和按秩合并优化下性能接近常数时间。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/939535.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Centos创建共享文件夹拉取文件

Centos创建共享文件夹拉取文件

1.打开VMware程序&#xff0c;鼠标右检你的虚拟机&#xff0c;打开设置 2.点击选项——共享文件夹——总是启用 点击添加&#xff0c;设置你想要共享的文件夹在pc上的路径&#xff08;我这里已经添加过了就不加了&#xff09; 注意不要中文&#xff0c;建议用share&#xff0c…
阅读更多...
Element@2.15.14-tree checkStrictly 状态实现父项联动子项，实现节点自定义编辑、新增、删除功能

Element@2.15.14-tree checkStrictly 状态实现父项联动子项，实现节点自定义编辑、新增、删除功能

背景&#xff1a;现在有一个新需求&#xff0c;需要借助树结构来实现词库的分类管理&#xff0c;树的节点是不同的分类&#xff0c;不同的分类可以有自己的词库&#xff0c;所以父子节点是互不影响的&#xff1b;同样为了选择的方便性&#xff0c;提出了新需求&#xff0c;选择…
阅读更多...
java版电子招投标采购|投标|评标|竞标|邀标|评审招投标系统源码

java版电子招投标采购|投标|评标|竞标|邀标|评审招投标系统源码

招投标管理系统是一款适用于招标代理、政府采购、企业采购和工程交易等领域的企业级应用平台。该平台以项目为主线&#xff0c;从项目立项到项目归档&#xff0c;实现了全流程的高效沟通和协作。通过该平台&#xff0c;用户可以实时共享项目数据信息&#xff0c;实现规范化管理…
阅读更多...
【Verilog HDL 入门教程】 —— 学长带你学Verilog（基础篇）

【Verilog HDL 入门教程】 —— 学长带你学Verilog（基础篇）

文章目录 一、Verilog HDL 概述1、Verilog HDL 是什么2、Verilog HDL产生的背景3、Verilog HDL 和 VHDL的区别 二、Verilog HDL 基础知识1、Verilog HDL 语言要素1.1、命名规则1.2、注释符1.3、关键字1.4、数值1.4.1、整数及其表示1.4.2、实数及其表示1.4.3、字符串及其表示 2、…
阅读更多...
龙迅#LT7911E适用于EDP/DP/TPYE-C转MIPIDSI应用,支持图像处理功能,内置I2C，主应用副屏显示，投屏领域！

龙迅#LT7911E适用于EDP/DP/TPYE-C转MIPIDSI应用,支持图像处理功能,内置I2C，主应用副屏显示，投屏领域！

1. 描述 LT7911E 是一款高性能 eDP 转 MIPI D-PHY 转换器&#xff0c;旨在将 eDP 源连接到 MIPI 显示面板。 LT7911E 集成了一个符合 eDP1.4 标准的接收器&#xff0c;支持 1.62Gbps 至 5.67Gbps 的输入数据&#xff0c;以 270Mbps 的递增步长&#xff0c;以及一个 2 端口 D…
阅读更多...
《算法SM9》题目

《算法SM9》题目

判断题 SM9密码算法系统参数由KGC选择。 A.正确 B.错误 正确答案A 多项选择题 SM9密码算法KGC是负责&#xff08; &#xff09;的可信机构。 A.选择系统参数 B.生成主密钥 C.生成用户标识 D.生成用户私钥 正确答案ABD 判断题 SM9密钥封装机制封装的秘密密钥是根据…
阅读更多...
C语言——实现求出最大值

C语言——实现求出最大值

问题描述&#xff1a;利用C语言自定义函数求出一维数组里边最大的数字 //利用函数找最大数#include<stdio.h>int search(int s[9]) //查找函数 {int i , max s[0] , max_xia 0;for(i0;i<9;i){if(s[i] > max){max_xia i;max s[max_xia];}}return max; } in…
阅读更多...
【尚硅谷 - SSM+SpringBoot+SpringSecurity框架整合项目 】项目打包并且本地部署

【尚硅谷 - SSM+SpringBoot+SpringSecurity框架整合项目 】项目打包并且本地部署

前后端分离开发&#xff1a;把一个项目拆成两部分进行开发&#xff0c;所以在打包的时候&#xff0c;需要使用不同的打包方式。 后端 – SpringBoot – jar包 前端 – Vue: 因为使用了vue-admin-template框架&#xff1a;所以先使用框架进行打包使用Nginx部署&#xff0c;通…
阅读更多...
【SH】Ubuntu Server 24服务器搭建MySQL数据库研发笔记

【SH】Ubuntu Server 24服务器搭建MySQL数据库研发笔记

文章目录 搭建服务器在线安装1. 更新软件包列表2. 安装MySQL3. 检查MySQL状态4. 修改密码5. 新增用户6. 设置局域网访问 离线安装下载安装包 常用命令参考文档在线安装日志 搭建服务器 作者羊大侠搭建的是 Ubuntu Server 24.04 LTS 服务器环境 搭建参考文档&#xff1a;【SH】…
阅读更多...
容器化技术全面解析：Docker 与 Containerd 的深入解读

容器化技术全面解析：Docker 与 Containerd 的深入解读

目录 Docker 简介 1. 什么是 Docker&#xff1f; 2. Docker 的核心组件 3. Docker 的主要功能 4. Docker 的优点 5. Docker 的使用场景 Containerd 简介 1. 什么是 Containerd&#xff1f; 2. Containerd 的核心特性 3. Containerd 的架构 4. Containerd 与 Docker 的…
阅读更多...
华为数通最新题库 H12-821 HCIP稳定过人中

华为数通最新题库 H12-821 HCIP稳定过人中

以下是成绩单和考试人员 HCIP H12-831 HCIP H12-725 安全中级
阅读更多...
Webots控制器编程

Webots控制器编程

本文主要内容是如何编写Webots控制器&#xff0c;使用语言为Python。 文章目录 1. 新增控制器2. Hello World Example3. 读取传感器4. 使用执行器5. 理解step和robot.step函数6. 同时使用传感器和执行器7. 控制器参数 1. 新增控制器 对机器人Robot新增控制器的方式&#x…
阅读更多...
[SAP ABAP] 将内表数据转换为HTML格式

[SAP ABAP] 将内表数据转换为HTML格式

从sflight数据库表中检索航班信息&#xff0c;并将这些信息转换成HTML格式&#xff0c;然后下载或显示在前端 开发步骤 ① 自定义一个数据类型 ty_sflight 来存储航班信息 ② 声明内表和工作区变量&#xff0c;用于存储表头、字段、HTML内容和航班详细信息以及创建字段目录lt…
阅读更多...
《算法SM4》题目

《算法SM4》题目

单项选择题 我国商用密码算法SM4迭代结构是&#xff08;&#xff09;。 A.平衡Fesitel网络结构 B.非平衡Fesitel网络结构 C.SP结构 D.MD结构 正确答案B 多项选择题 SM4分组密码算法轮函数中的T置换&#xff0c;包括的运算有&#xff08;&#xff09;。 A.非线性变换 …
阅读更多...
深度学习革新音乐转录

深度学习革新音乐转录

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…
阅读更多...
Flink2.0未来趋势中需要注意的一些问题

Flink2.0未来趋势中需要注意的一些问题

手机打字&#xff0c;篇幅不长&#xff0c;主要讲一下FFA中关于Flink2.0的未来趋势&#xff0c;直接看重点。 Flink Forward Asia 2024主会场有一场关于Flink2.0的演讲&#xff0c;很精彩&#xff0c;官方也发布了一些关于Flink2.0的展望和要解决的问题。 1.0时代和2.0时代避免…
阅读更多...
EasyPlayer.js播放器Web播放H.265要兼顾哪些方面？

EasyPlayer.js播放器Web播放H.265要兼顾哪些方面？

在数字化时代&#xff0c;流媒体技术已经成为信息传播和娱乐消费的重要方式。随着互联网技术的飞速发展和移动设备的普及&#xff0c;流媒体服务正在重塑我们的生活和工作方式。从视频点播、在线直播到音乐流媒体&#xff0c;流媒体技术的广泛应用不仅改变了内容的分发和消费模…
阅读更多...
在 Solana 上实现 SOL 转账及构建支付分配器

在 Solana 上实现 SOL 转账及构建支付分配器

与以太坊不同&#xff0c;在以太坊中&#xff0c;钱包通过 msg.value 指定交易的一部分并“推送” ETH 到合约&#xff0c;而 Solana 程序则是从钱包“拉取” Solana。 因此&#xff0c;没有“可支付”函数或“msg.value”这样的概念。 下面我们创建了一个新的 anchor 项目&a…
阅读更多...
灵活接入第三方接口，解析第三方json数据,返回我们想要的json格式

灵活接入第三方接口，解析第三方json数据,返回我们想要的json格式

需求&#xff1a;我想接入任意第三方http 接口&#xff08;暂不考虑鉴权问题&#xff09;、接口返回任意json数据。 1、要求返回的json数据通过我的R< T > 返回。 2、我的R< T > 里面包含参数 data&#xff0c;code&#xff0c;msg&#xff0c;success标识。 3、…
阅读更多...
ExcelVBA编程输出ColorIndex与对应颜色色谱

ExcelVBA编程输出ColorIndex与对应颜色色谱

标题 ExcelVBA编程输出ColorIndex与对应颜色色谱 正文 解决问题编程输出ColorIndex与对应色谱共56&#xff0c;打算分4纵列输出&#xff0c;标题是ColorIndex,Color,Name 1. 解释VBA中的ColorIndex属性 在VBA&#xff08;Visual Basic for Applications&#xff09;中&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023