【高阶数据结构】并查集

news/2024/11/10 15:10:23/

并查集

  • 1.并查集原理
  • 2.并查集实现
  • 3.并查集应用

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励，我们一起努力吧!😃😃

并查集实际是一个森林，森林是由多棵互不相交的树组成的。那什么数据结构能把多颗树存下来呢？下面随着我们的学习就知道了。

1.并查集原理

在一些应用问题中，需要将n个不同的元素划分成一些不相交的集合。开始时，每个元素自成一个单元素集合，然后按一定的规律将归于同一组元素的集合合并。在此过程中要反复用到查询某一个元素归属于那个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find set)。

比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不同的学校，起先互不相识，每个学生都是一个独立的小团体，去了之后因为地域问题大家吃饭不一样，因此分成了三个小团体。那怎么表示这三个不同的集合呢？

并查集！就是把不同的元素分到不同的集合。还涉及当两个集合有交集的时候还可能将集合合并。并查集查你在那个集合，还合并集合！

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

在这里插入图片描述

可能会有这样的问题，内部给他们编号，万一外面给的是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]);_IndexMap[a[i]] = i;}}private:vector<T> _a;          //编号找人map<T, int> _IndexMap; //人找编号
};int main()
{string arr[] = { "张三","李四","王五","赵六" };UnionFindSet<string> ufs(arr, 4);return 0;
}

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

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

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

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

在这里插入图片描述

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

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

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

在这里插入图片描述

合并过程：

比如说0和6先合并，将6位置的-1加到0位置，0位置就是-2，然后6位置保存0位置的下标。0和7合并也是将7位置的-1集到0位置，0位置就是-3，然后7位置保存0位置的下标。。。。

在这里插入图片描述

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

在这里插入图片描述

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

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

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

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

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

在这里插入图片描述

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

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

下面就实现一下并查集

2.并查集实现

这里我们简单一些，不搞映射关系，假设它直接给的是下标。

class UnionFindSet
{
public:UnionFindSet(int sz):_ufs(sz,-1)// 初始时，将数组中元素全部设置为1{}//合并集合bool Union(int x1, int x2){//找到对应的根，让根进行合并int root1 = FindRoot(x1);int root2 = FindRoot(x2);// 如果本身就是在一个集合就没有必须合并了if (root1 == root2)return false;//这里可以让小的做根if(root1 > root2)swap(root1,root2);// 将两个集合中元素合并_ufs[root1] += _ufs[root2];// 将其中一个集合名称改变成另外一个_ufs[root2] = root1;return true;}// 给一个元素的编号，找到该元素所在集合的名称int FindRoot(int x){int parent = x;while (_ufs[parent] >= 0)// 如果数组中存储的是负数，找到，否则一直继续{parent = _ufs[parent];}return parent;}bool IsSet(int x1, int x2){return FindRoot(x1) == FindRoot(x2);}// 数组中负数的个数，即为集合的个数size_t SetSize(){size_t sz= 0;for (auto e : _ufs){if (e < 0) ++sz;}return sz;}private:vector<int> _ufs;
};

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

在这里插入图片描述

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

一般在查找根的时候去压缩。查找谁就把它这一条路径压缩。找到根之后判断一下，如果它的父亲就是根就不用压缩，如果不是说明中间有间隔层，然后就可以把这条路径压缩。比如是这个4，首先先把4变成2的孩子，然后将4的父亲1也去变成2的孩子，这条路径都可以变成2的孩子。

在这里插入图片描述

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;
}

还有一种提高效率的方式，比如两个集合合并的时候，控制数据量小的向数据量大的合并。因为合并相当于一个集合向下压一层，是100个向下压一层还是20个向下压一层更好呢，显然是数据量小的向下压一层。

	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;}

并查集完整代码

#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.并查集应用

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

题目描述：

在这里插入图片描述

这里我们就可以用到并查集的思想，将同一个省份的放到一个集合，最后在统计并查集中有几个集合就是省份的数量。

难道我们要自己手撕一个并查集写上去嘛？其实并不用，并查集中最重要的就是Findroot找根和合并集合。只要我们知道并查集内部怎么实现的，我们只用它的核心功能就可以了。

class Solution {
public: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 < isConnected.size(); ++i){for(int j = 0; j < isConnected[i].size(); ++j){if(isConnected[i][j] == 1){// 合并集合int root1 = Findroot(i);int root2 = Findroot(j);if(root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}}}}int count = 0;for(auto e : ufs){if(e < 0)++count;}return count;}
};

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

题目描述：

在这里插入图片描述

它的意思就是让看一看，给的方程组有没有相背。就如 a == b，b != a 这给的就有问题。怎么用并查集解决这里的问题？

把所有元素看成独立的集合，我们可以把两个元素之间是相等关系的元素合并到同一个集合，如果两个元素之间是不相等的关系的元素出现在同一个集合就有问题了。

class Solution {
public: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& str : equations){if(str[1] == '='){int root1 = Findroot(str[0] - 'a');int root2 = Findroot(str[3] - 'a');if(root1 != root2){ufs[root1] += ufs[root2];ufs[root2] = root1;}}}//第二遍,如果不相等的值在相同的集合,就违背了for(auto& str : equations){if(str[1] == '!'){int root1 = Findroot(str[0] - 'a');int root2 = Findroot(str[3] - 'a');if(root1 == root2)return false;}}return true;}
};

http://www.ppmy.cn/news/1501965.html

相关文章

使用java读取本地文件内容并输出，java读取文件内容，节省内存开销

使用java读取本地文件内容并输出，java读取文件内容，节省内存开销

java使用FileInputStream读取本地文件内容 java使用Stream流读取本地文件内容 1.先在自己笔记本选一个目录创建文件&#xff0c;这里就选择在D盘创建一个 word.txt文件 随意输入内容例如 2.直接来直接复制代码运行 import java.io.*; import java.nio.file.Files; import ja…
阅读更多...
计算机毕业设计选题推荐-智能推荐旅游平台-Java项目实战

计算机毕业设计选题推荐-智能推荐旅游平台-Java项目实战

✨作者主页&#xff1a;IT研究室✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Python…
阅读更多...
springboot整合 knife4j 接口文档

springboot整合 knife4j 接口文档

第一步&#xff1a;引入依赖 <dependency><groupId>com.github.xiaoymin</groupId><artifactId>knife4j-openapi2-spring-boot-starter</artifactId><version>4.4.0</version></dependency> 第二步&#xff1a;写入配置 方…
阅读更多...
137.只出现一次的数字Ⅱ

137.只出现一次的数字Ⅱ

1.题目描述 给你一个整数数组 nums &#xff0c;除某个元素仅出现 一次 外&#xff0c;其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。 你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。 示例 1&#xff1a; 输入&#xff1a;nums …
阅读更多...
[C++]类的自动转换和强制类型转换

[C++]类的自动转换和强制类型转换

在C中&#xff0c;类的自动转换&#xff08;也称为隐式转换&#xff09;和强制类型转换&#xff08;显式转换&#xff09;是面向对象编程中处理类型之间转换的两种重要机制。这些转换允许程序员定义如何在不同类型&#xff08;特别是自定义类型&#xff09;之间安全地交换数据。…
阅读更多...
JDK新特性（Lambda表达式，Stream流）

JDK新特性（Lambda表达式，Stream流）

Lambda表达式&#xff1a; Lambda 表达式背后的思想是函数式编程&#xff08;Functional Programming&#xff09;思想。在传统的面向对象编程中&#xff0c;程序主要由对象和对象之间的交互&#xff08;方法调用&#xff09;构成&#xff1b;而在函数式编程中&#xff0c;重点…
阅读更多...
操作系统面试知识点总结5

操作系统面试知识点总结5

#来自ウルトラマンメビウス&#xff08;梦比优斯&#xff09; 1 IO管理概述 1.1 I/O 设备 I/O 设备的类型分类。 1.1.1 按使用特性 人机交互类外部设备&#xff0c;例如打印机、显示器等。存储设备&#xff0c;例如磁盘、光盘等。网络通信设备&#xff0c;例如网络接口等。 1…
阅读更多...
谷粒商城实战笔记-75-商品服务-API-品牌管理-品牌分类关联与级联更新

谷粒商城实战笔记-75-商品服务-API-品牌管理-品牌分类关联与级联更新

文章目录 一&#xff0c;引入Mybatis Plus分页插件二&#xff0c;品牌列表的模糊查询三&#xff0c;增加品牌测试数据四&#xff0c;开发后台品牌关联分类接口1&#xff0c;接口product/categorybrandrelation/catelog/list2&#xff0c;接口product/categorybrandrelation/sav…
阅读更多...
最新文章

Copyright @ 2022~2023