其它高阶数据结构①_并查集（概念+代码+两道OJ）

目录

1. 并查集的概念

2. 并查集的实现

3. 并查集的应用

3.1 力扣LCR 116. 省份数量

解析代码1

解析代码2

3.2 力扣990. 等式方程的可满足性

解析代码

本篇完。

写在前面：

        此高阶数据结构系列，虽然放在⑤数据结构与算法专栏，但还是作为一个拓展学习，建议跳过第⑤序号跟着其它专栏序号学，当时是想着要期末考和考研的同学，考到图才开这个专栏的吧，其他不急的同学可以在学完MySQL专栏后再看，此系列也放在了⑩其它高阶数据结构专栏，这里简单学习并查集是为了下一个数据结构“图”的学习。

1. 并查集的概念

  • 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。
  • 并查集通常用森林来表示，森林中的每棵树表示一个集合，树中的结点对应一个元素。

        虽然利用其它数据结构也能完成不相交集合的合并及查询，但在数据量极大的情况下，其耗费的时间和空间也是极大的。

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

        并查集是多个独立集合的合集，用于表示数据之间的关系，并查集中的每一个集合是用多叉树来表示的。

        比如：某公司今年校招全国总共招生10人，西安招4人，成都招3人，武汉招3人，10个人来自不 同的学校，起先互不相识，每个学生都是一个独立的小团体，现给这些学生进行编号：{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; 给以下数组用来存储该小集体，数组中的数字代表：该小集体中具有成员的个 数。数组中某个位置的值为负数，表示该位置是树的根，这个负数的绝对值表示的这棵树（集合）中数据的个数，因为刚开始每个人各自属于一个集合，所以将数组中的位置都初始化为-1。

        毕业后，学生们要去公司上班，每个地方的学生自发组织成小分队一起上路，于是：西安学生小分队s1={0,6,7,8}，成都学生小分队s2={1,4,9}，武汉学生小分队s3={2,3,5}就相互认识了，10个人形成了三个小团体。假设右三个群主0,1,2担任队长，负责大家的出行。

一趟火车之旅后，每个小分队成员就互相熟悉，称为了一个朋友圈。

        从上图可以看出：编号6,7,8同学属于0号小分队，该小分队中有4人(包含队长0)；编号为4和9的同 学属于1号小分队，该小分队有3人(包含队长1)，编号为3和5的同学属于2号小分队，该小分队有3 个人(包含队长1)。 仔细观察数组中内变化，可以得出以下结论：

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

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

        现在0集合有7个人，2集合有3个人，总共两个朋友圈。通过以上例子可知，并查集一般可以解决一下问题：

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

2. 并查集的实现

代码实现还是很简单的，直接放出代码：（建议复制到自己编译器跟着注释一起看）

#pragma once

#include <iostream>
#include <vector>
using namespace std;

class UnionFindSet
{
private:
    vector<int> _ufs;

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

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

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

            index = parent;
        }
        return index;
    }

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

    bool Union(int x1, int x2) // 合并两个集合
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

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

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

        _ufs[root1] += _ufs[root2]; // 负号代表根，数字代表该集合中元素个数

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

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

void TestUFS()
{
    UnionFindSet u(10);

    u.Union(0, 6);
    u.Union(7, 6);
    u.Union(7, 8);

    u.Union(1, 4);
    u.Union(4, 9);

    u.Union(2, 3);
    u.Union(2, 5);

    u.FindRoot(6);
    u.FindRoot(9);

    cout << u.Count() << endl;
}

3. 并查集的应用

直接复制上面并查集的代码到力扣写两道题：

3.1 力扣LCR 116. 省份数量

LCR 116. 省份数量

难度 中等

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

提示：

  • 1 <= n <= 200
  • n == isConnected.length
  • n == isConnected[i].length
  • isConnected[i][j] 为 1 或 0
  • isConnected[i][i] == 1
  • isConnected[i][j] == isConnected[j][i]

注意：本题与主站 547 题相同： 547. 省份数量

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {

    }
};

解析代码1

直接复制并查集过来：

class UnionFindSet
{
private:
    vector<int> _ufs;

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

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

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

            index = parent;
        }
        return index;
    }

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

    bool Union(int x1, int x2) // 合并两个集合
    {
        int root1 = FindRoot(x1);
        int root2 = FindRoot(x2);

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

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

        _ufs[root1] += _ufs[root2]; // 负号代表根，数字代表该集合中元素个数

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

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

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        UnionFindSet ufs(isConnected.size());
        for (size_t i = 0; i < isConnected.size(); ++i)
        {
            for (size_t j = 0; j < isConnected[i].size(); ++j)
            {
                if (isConnected[i][j] == 1) // 合并集合
                {
                    ufs.Union(i, j);
                }
            }
        }
        return ufs.Count();
    }
};

解析代码2

用数组模拟并查集：

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        vector<int> ufs(isConnected.size(), -1); // 手动控制并查集
        auto findRoot = [&ufs](int x) // 查找根
        {
            while(ufs[x] >= 0)
                x = ufs[x];
            return x;
        };

        for(size_t i = 0; i < isConnected.size(); ++i)
        {
            for(size_t 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 cnt = 0;
        for(auto e : ufs)
        {
            if(e < 0)
                ++cnt;
        }
        return cnt;
    }
};

3.2 力扣990. 等式方程的可满足性

990. 等式方程的可满足性

难度 中等

给定一个由表示变量之间关系的字符串方程组成的数组，每个字符串方程 equations[i] 的长度为 4，并采用两种不同的形式之一："a==b" 或 "a!=b"。在这里，a 和 b 是小写字母（不一定不同），表示单字母变量名。

只有当可以将整数分配给变量名，以便满足所有给定的方程时才返回 true，否则返回 false。 

示例 1：

输入：["a==b","b!=a"]
输出：false
解释：如果我们指定，a = 1 且 b = 1，那么可以满足第一个方程，但无法满足第二个方程。没有办法分配变量同时满足这两个方程。

示例 2：

输入：["b==a","a==b"]
输出：true
解释：我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。

示例 3：

输入：["a==b","b==c","a==c"]
输出：true

示例 4：

输入：["a==b","b!=c","c==a"]
输出：false

示例 5：

输入：["c==c","b==d","x!=z"]
输出：true

提示：

  1. 1 <= equations.length <= 500
  2. equations[i].length == 4
  3. equations[i][0] 和 equations[i][3] 是小写字母
  4. equations[i][1] 要么是 '='，要么是 '!'
  5. equations[i][2] 是 '='
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {

    }
};

解析代码

并查集的变形，思路：

  1. 将所有"=="两端的字符合并到一个集合中。
  2. 检测"!=" 两端的字符是否在同一个集合中，如果在，不满足，如果不在，满足。
class Solution {
public:
    bool equationsPossible(vector<string>& equations) {
        vector<int> ufs(26, -1);
        auto findRoot = [&ufs](int x)
        {
            while(ufs[x] >= 0)
                x = ufs[x];
            return x;
        };

        for(auto& e : equations) // 第一遍，先把相等的值加到一个集合中
        {
            if(e[1] == '=')
            {
                int root1 = findRoot(e[0] - 'a');
                int root2 = findRoot(e[3] - 'a');
                if(root1 != root2)
                {
                    ufs[root1] += ufs[root2];
                    ufs[root2] = root1;
                }
            }
        }

        for(auto& e : equations) // 第二遍，判断相等在不在一个集合，在就相悖了
        {
            if(e[1] == '!')
            {
                int root1 = findRoot(e[0] - 'a');
                int root2 = findRoot(e[3] - 'a');
                if(root1 == root2)
                    return false;
            }
        }
        return true;
    }
};

本篇完。

这里简单学习并查集更多是为了下一个数据结构“图”的学习，一些竞赛的OJ也会用到并查集。

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

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

相关文章

2023年全国职业院校技能大赛（高职组）“云计算应用”赛项赛卷5（私有云）

2023年全国职业院校技能大赛（高职组）“云计算应用”赛项赛卷5（私有云）

#需要资源&#xff08;软件包及镜像&#xff09;或有问题的&#xff0c;可私聊博主&#xff01;&#xff01;&#xff01; #需要资源&#xff08;软件包及镜像&#xff09;或有问题的&#xff0c;可私聊博主&#xff01;&#xff01;&#xff01; #需要资源&#xff08;软件包…
阅读更多...
idea2023.3.2版本全局设置maven地址

idea2023.3.2版本全局设置maven地址

idea每次新建项目都默认使用了一个user目录下的地址&#xff0c;而不是自己安装的maven地址&#xff0c;每次创建项目后&#xff0c;都要重新从settings中设置一下maven地址。 可以全局修改&#xff1a;首先在File-->Close Project回到idea最开始的界面 然后在Customize里点…
阅读更多...
Spring Boot 整合讯飞星火3.5通过接口Api接口实现聊天功能（首发）复制粘贴即可使用，后续更新WebSocket实现聊天功能

Spring Boot 整合讯飞星火3.5通过接口Api接口实现聊天功能（首发）复制粘贴即可使用，后续更新WebSocket实现聊天功能

程序员必备网站&#xff1a; 天梦星服务平台 (tmxkj.top)https://tmxkj.top/#/ 1.pom.xml <dependency><groupId>com.alibaba</groupId><artifactId>fastjson</artifactId><version>1.2.72</version></dependency><depen…
阅读更多...
我和jetson-Nano的故事（10）——安装OpenCV3.2.0

我和jetson-Nano的故事（10）——安装OpenCV3.2.0

1. 仓库地址 opencv https://opencv.org/releases/page/6/opencv_contrib https://github.com/opencv/opencv_contrib/tree/3.2.0 2. cmake-gui安装 安装指令 sudo apt-get install cmake-qt-gui如果安装过程中入到下面的问题 可以按照以下方法解决 sudo apt --fix-broke…
阅读更多...
Cartographer前后端梳理

Cartographer前后端梳理

0. 简介 最近在研究整个SLAM框架的改进处&#xff0c;想着能不能从Cartographer中找到一些亮点可以用于参考。所以这一篇博客希望能够梳理好Cartographer前后端优化&#xff0c;并从中得到一些启发。carto整体是graph-based框架&#xff0c;前端是scan-map匹配&#xff0c;后端…
阅读更多...
SpringBoot自动装配（二）

SpringBoot自动装配（二）

近日&#xff0c;余溺于先贤古哲之文无法自拔。虽未明其中真意&#xff0c;但总觉有理。遂抄录一篇以供诸君品鉴——公孙鞅曰&#xff1a;“臣闻之&#xff1a;‘疑行无名&#xff0c;疑事无功。’君亟定变法之虑&#xff0c;殆无顾天下之议之也。且夫有高人之行者&#xff0c;…
阅读更多...
52岁「豹嫂」代夫尽孝送花畀奶奶被赞

52岁「豹嫂」代夫尽孝送花畀奶奶被赞

歌手胡蓓蔚与「豹哥」单立文相爱28年&#xff0c;两人曾上节目分享婚姻之道&#xff0c;指婚姻最紧要有忍耐力&#xff0c;要抗拒引诱。其实除了忍耐力&#xff0c;胡蓓蔚和奶奶相处都有一套。 早前单立文带胡蓓蔚及妈妈到米芝连一星餐厅叹美食&#xff0c;庆祝奶奶89岁生日&am…
阅读更多...
数据结构之二叉树详解[1]

数据结构之二叉树详解[1]

在前面我们介绍了堆和二叉树的基本概念后&#xff0c;本篇文章将带领大家深入学习链式二叉树。 1.预备知识 2.二叉树结点的创建 3.二叉树的遍历 3.1前序遍历 3.2中序遍历 3.3 后序遍历 4.统计二叉树的结点个数 5.二叉树叶子结点的个数 6.二叉树第k层的结点个数 7.总结 …
阅读更多...
如何使用恢复模式修复Mac启动问题？这里提供详细步骤

如何使用恢复模式修复Mac启动问题？这里提供详细步骤

如果你的Mac无法启动，不要惊慌，Mac有一个隐藏的恢复模式，你可以使用它来诊断和修复任何问题，或者在需要时完全重新安装macOS。以下是如何使用它。 如何在Mac上启动到恢复模式 你需要做的第一件事是启动到恢复模式。尽管操作说明会因你使用的Mac电脑而异，但幸运的是，启动…
阅读更多...
[数据结构1.0]快速排序

[数据结构1.0]快速排序

最近学习了快速排序&#xff0c;鼠鼠俺来做笔记了&#xff01; 本篇博客用排升序为例介绍快速排序&#xff01; 1.快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法&#xff0c;其基本思想为&#xff1a;任取待排序元素序列中的某元素作为基准值&#x…
阅读更多...
(四)Spring教程——控制反转或依赖注入与Java的反射技术

(四)Spring教程——控制反转或依赖注入与Java的反射技术

IoC的底层实现技术是反射技术&#xff0c;目前Java、C#、PHP 等语言均支持反射技术。 在运行状态中&#xff0c;对于任意一个类&#xff0c;都能够获取到这个类的所有属性和方法&#xff1b;对任意一个对象&#xff0c;都能够调用它的任意方法和属性&#xff08;包括私有的方法…
阅读更多...
【数据可视化01】matplotlib实例3之数据统计

【数据可视化01】matplotlib实例3之数据统计

目录 一、引言二、实例介绍1.百分位数为横条形图2.箱线图定制化3.带有自定义填充颜色的箱线图4.箱线图5.箱线图和小提琴图6.二维数据集的置信椭圆 一、引言 matplotlib库 可以用来创建各种静态、动态、交互式的图形&#xff0c;并广泛应用于数据分析和数据可视化领域。 二、实…
阅读更多...
6. 第K小的和-二分

6. 第K小的和-二分

6.第K小的和 - 蓝桥云课 (lanqiao.cn) #include <bits/stdc.h> #define int long long #define endl \n using namespace std; int n,m,k,an[100005],bm[100005]; int check(int x){int res0;//序列C中<x的数的个数for(int i0;i<n;i){//遍历数组A&#xff0c;对于每…
阅读更多...
【Linux】如何在Linux中配置自己的环境变量？

【Linux】如何在Linux中配置自己的环境变量？

文章目录 配置环境变量方法一&#xff1a;【>>】使用追加重定向方法二&#xff1a;使用【export PATH$PATH:/路径】(推荐) 配置环境变量 那要怎么去将一个系统路径添加到【环境变量】中呢 方法一&#xff1a;【>>】使用追加重定向 &#x1f6a9;这里一定要主要覆盖…
阅读更多...
mongodb备份还原指南

mongodb备份还原指南

MongoDB 提供的命令行实用程序mongodump和mongorestore创建备份和恢复数据的过程。 一、数据备份 mongorestore和mongodump实用程序可处理BSON数据转储&#xff0c;对于创建小型部署的备份非常有用。要实现弹性且无中断的备份&#xff0c;请将文件系统快照或区块级磁盘快照与…
阅读更多...
Git 的原理与使用（中）

Git 的原理与使用（中）

Git 的原理与使用&#xff08;上&#xff09;中介绍了Git初识&#xff0c;Git的安装与初始化以及工作区、暂存区、版本库相关的概念与操作&#xff0c;本文接着上篇的内容&#xff0c;继续深入介绍Git在的分支管理与远程操作方面的应用。 目录 五、分支管理 1.理解分支 2.创…
阅读更多...
免费Premiere模板，几何图形元素动画视频幻灯片模板素材下载

免费Premiere模板，几何图形元素动画视频幻灯片模板素材下载

Premiere Pro模板&#xff0c;几何图形元素动画视频幻灯片模板 &#xff0c;组织良好&#xff0c;易于自定义。包括PDF教程。 项目特点&#xff1a; 使用Adobe Premiere Pro 2021及以上版本。 19201080全高清。 不需要插件。 包括帮助视频。 免费下载&#xff1a;https://prmu…
阅读更多...
PyQt6--Python桌面开发（14.QCommandLinkButton命令链接按钮控件）

PyQt6--Python桌面开发（14.QCommandLinkButton命令链接按钮控件）

QCommandLinkButton命令链接按钮控件
阅读更多...
Java毕业设计 基于SpringBoot vue药店管理系统

Java毕业设计 基于SpringBoot vue药店管理系统

Java毕业设计 基于SpringBoot vue药店管理系统 SpringBoot 药店管理系统 功能介绍 员工 登录 个人中心 修改密码 个人信息 查看供应商信息 查看药品 查看进货 查看销售 管理员 登录 个人中心 修改密码 个人信息 供应商类型管理 供应商信用等级类型管理 药品类型管理 供应商信…
阅读更多...
【Web后端】MVC模式

【Web后端】MVC模式

1、简介 MVC模式&#xff0c;全称Model-View-Controller&#xff08;模型-视图-控制器&#xff09;模式&#xff0c;是一种软件设计典范&#xff0c;它将应用程序的用户界面&#xff08;视图&#xff09;和业务逻辑&#xff08;模型&#xff09;分离&#xff0c;同时提供了一个…
阅读更多...
最新文章

Copyright @ 2022~2023