当前位置: 首页 > news >正文

数据结构——

1. 什么是并查集?

在计算机科学中,并查集(英文:Disjoint-set data structure,直译为不数据结构交集)是一种数据结构,用于处理一些不交集(Disjoint sets,一系列没有重复元素的集合)的合并及查询问题。

举个简单的例子

一个组织里来个10个新人,它们的编号为从1~10,假设此时它们根据彼此的老家而互相亲近(即形成一个小团体),我们要将这10个人划分成不同的小团体,这样划分后形成的结果就是并查集。

接下来我们就来模拟这10个人的划分过程,首先我们可以将每个人的初始值设置为-1,当两个人都属于同一个小团体时,将其中一个人的-1加到另一个人身上,自己的值指向另一个人的下标, 此时另一个人就作为这一个小团体的,这之后如果有新的人进入这个团体,将新人的-1加到根上,再让新人指向根的下标。这样操作后,所有人中只要自己的值<0,则表明自己是一个团队的根,绝对值表示团队人数,而团体中的其他人均指向这个根。

2. 并查集的常见操作

我们通过上面的模拟,我们可以发现并查集的主要操作主要是:合并查找根查看团队个数

我们使用C++实现这个数据结构有

#pragma once
#include <vector>using namespace std;class UnionFindSet
{
public:// 将并查集中的所有元素初始化为-1UnionFindSet(size_t n):_ufs(n, -1){}// 查找根int FindRoot(int x);// 合并void Union(int x1, int x2);// 查看集合个数size_t UnionCount(int x);private:vector<int> _ufs; 
};

1. 查找根

// 查找根
int FindRoot(int x)
{if (x >= _ufs.size()){throw invalid_argument("无效参数!");return -1;}int root = x;while (_ufs[root] >= 0) // 不为根就向上查找{root = _ufs[root];}return root;
}

2. 合并

在合并时,有可能会出现两个团队互相合并的情况,此时我们只需要将其中一个团队的根的值加到另一个团队的根上,再让自己指向另一个团队的根即可,即

// 合并
void Union(int x1, int x2)
{int root1 = FindRoot(x1);int root2 = FindRoot(x2);// 两个人属于不同的集合时,才需要进行合并if (root1 != root2){_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}
}

3. 查看集合个数

// 查看集合个数
size_t UnionCount()
{size_t ret = 0;for (auto& e : _ufs){if (e < 0) ret++;}return ret;
}

3. 并查集的实际应用

1. 省份数量

题目链接:LCR 116. 省份数量 - 力扣(LeetCode)

解析:分析题目,如果这道题使用并查集就没有那么难,整体思路就是如果两个城市相连就将他们合并为一个省份,最终返回省份个数即可

解法一:使用并查集数据结构

class UnionFindSet
{
public:// 将并查集中的所有元素初始化为-1UnionFindSet(size_t n):_ufs(n, -1){}// 查找根int FindRoot(int x){if (x >= _ufs.size()){throw invalid_argument("无效参数!");return -1;}int root = x;while (_ufs[root] >= 0) // 不为根就向上查找{root = _ufs[root];}return root;}// 合并void Union(int x1, int x2){int root1 = FindRoot(x1);int root2 = FindRoot(x2);// 两个人属于不同的集合时,才需要进行合并if (root1 != root2){_ufs[root1] += _ufs[root2];_ufs[root2] = root1;}}// 查看集合个数size_t UnionCount(){size_t ret = 0;for (auto& e : _ufs){if (e < 0) ret++;}return ret;}private:vector<int> _ufs;
};class Solution
{
public:int findCircleNum(vector<vector<int>>& isConnected){UnionFindSet ufs(isConnected.size());for (int i = 0; i < isConnected.size(); i++)for (int j = 0; j < isConnected[i].size(); j++)if (isConnected[i][j] == 1){ufs.Union(i, j);}return ufs.UnionCount();}
};

 解法二:直接运用并查集思想

2. 等式方程的可满足性

题目链接:990. 等式方程的可满足性 - 力扣(LeetCode)

http://www.lryc.cn/news/384120.html

相关文章:

  • 微信小程序建议录音机
  • 双指针:移动零
  • 图像亮度和对比度的调整
  • Linux加固-权限管理_chattr之i和a参数
  • windows10/win11截图快捷键 和 剪贴板历史记录 快捷键
  • 上海计算机考研避雷,25考研慎报
  • 第九次作业
  • A股探底回升,跑出惊天大阳,你们知道为什么吗?
  • jenkins nginx自动化部署 php项目
  • 海外代理IP哪个可靠?如何测试代理的稳定性?
  • MySQL之可扩展性(四)
  • JupyterLab使用指南(三):JupyterLab的Cell详细介绍
  • solidity智能合约如何实现跨合约调用函数
  • 关于Vue2的生命周期会问到哪些面试题?
  • 尚品汇-(七)
  • 【Python datetime模块精讲】:时间旅行者的日志,精准操控日期与时间
  • keepalived 服务高可用(简约版)
  • 【前端】Vue项目和微信小程序生成二维码和条形码
  • 同时使用接口文档swagger和knife4j
  • Compose - 权限申请
  • 第十九条:要么为继承而设计并提供文档说明,要么就禁止继承
  • Node.js全栈指南:浏览器显示一个网页
  • Linux远程桌面(Ubuntu/Deepin)——安装和使用 VNC 及通过 noVNC 实现浏览器实现远程桌面访问教程
  • 2024年最新通信安全员考试题库
  • SpringMVC系列八: 手动实现SpringMVC底层机制-下
  • 【昇思初学入门】第八天打卡-模型保存与加载
  • 喜报!极限科技新获得一项国家发明专利授权:“搜索数据库的正排索引处理方法、装置、介质和设备”
  • 深入探讨:UART与USART在单片机中串口的实际应用与实现技巧
  • Windows上PyTorch3D安装踩坑记录
  • 操作符详解(上) (C语言)