并查集

本文用于个人算法竞赛学习,仅供参考

目录

一.什么是并查集

二.并查集实现

三.路径优化

四.时间复杂度

五.并查集+路径压缩 模板

五.题目


一.什么是并查集

并查集(Disjoint Set)是一种数据结构,用于处理一系列不相交的集合的合并与查询问题。并查集主要支持两种操作:

1. 合并(Union):将两个集合合并为一个集合。
2. 查询(Find):确定一个元素属于哪个集合,通常用于判断两个元素是否属于同一个集合。

并查集通常使用树结构来表示集合,其中每个节点表示一个元素,树的根节点表示集合的代表元素。通过路径压缩和按秩合并(没什么用)等优化方式,可以在近似常数时间内进行合并和查询操作。

二.并查集实现

1.存储方式

使用一维数组来实现,通过数组将元素连通在一起,就相当于将元素放在同一个集合中了。比如将A、B、C放在同一个集合,有

2.功能实现

const int N = 10010;
int father[N];

//并查集寻根的过程--递归
int find(int u)
{
	//等于本身就是根节点,返回根节点
	if (u == father[u])
		return u;
	//不是根节点,向下寻根
	else
		return find(father[u]);
}

// v -> u加入这条边
void join(int u, int v)
{
	u = find(u);//寻根
	v = find(v);//寻根
	//同一集合就不用加入了
	if (u == v)
		return;
	father[v] = u;
}

//判断是否同一个集合---是否同一个根
bool isSame(int u, int v)
{
	u = find(u);//寻根
	v = find(v);//寻根
	return u == v;
}

//初始化---每个节点初始化指向自己
void init()
{
	for (int i = 0; i < N; i++)
	{
		father[i] = i;
	}
}

三.路径优化

对于一个集合,将其抽象成树形结构可能是:

 对于find函数,其实是一个寻根过程,比如

对于插入一条边和查询是否同一个集合,都是通过查找根节点后进行操作的,那么find的效率就取决于路径的长度,既然都是找根,那么同一个集合的元素直接插到同一个节点不就行了,将树的结构改成:

这样每次find就不用递归那么多层了,这种思想就是路径压缩。

只需要改一下find函数就可以实现:
 

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}

四.时间复杂度

路径压缩后的并查集时间复杂度在O(logn)与O(1)之间,且随着查询或者合并操作的增加,时间复杂度会越来越趋于O(1)。 

五.并查集+路径压缩 模板

const int N = 10010;
int father[N];

//并查集寻根的过程--递归
int find(int u)
{
	return u == father[u] ? u : father[u] = find(father[u]);
}

// v -> u加入这条边
void join(int u, int v)
{
	u = find(u);//寻根
	v = find(v);//寻根
	//同一集合就不用加入了
	if (u == v)
		return;
	father[v] = u;
}

//判断是否同一个集合---是否同一个根
bool isSame(int u, int v)
{
	u = find(u);//寻根
	v = find(v);//寻根
	return u == v;
}

//初始化---每个节点初始化指向自己
void init()
{
	for (int i = 0; i < N; i++)
	{
		father[i] = i;
	}
}

五.题目

 1971. 寻找图中是否存在路径 - 力扣(LeetCode)

class Solution {
    //并查集
    //模板实现
private:
    int n = 200005;
    vector<int> father = vector<int>(n, 0);
    //初始化
    void init()
    {
        for(int i = 0; i < n; i++)
        {
            father[i] = i;
        }   
    }
    //find找根,路径压缩实现
    int find(int u)
    {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    //判断是否同根
    bool isSame(int u, int v)
    {
        u = find(u);
        v = find(v);
        return u == v;
    }
    //加入同一集合 v -> u
    void join(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v)
        {
            return;
        }
        father[v] = u;
    }

    public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        init();
        for(int i = 0; i < edges.size(); i++)
        {
            join(edges[i][0], edges[i][1]);
        }
        return isSame(source,destination);
    }
};

 684. 冗余连接 - 力扣(LeetCode)

class Solution {
    //并查集
private:
    int n = 1005;
    vector<int> father = vector<int>(n, 0);
    //初始化
    void init()
    {
        for(int i = 0; i < n; i++)
        {
            father[i] = i;
        }
    }
    //查找&&并查集
    int find(int u)
    {
        return father[u] == u ? u : father[u] = find(father[u]);
    }
    //判断是否同一跟根节点
    bool isSame(int u, int v)
    {
        u = find(u);
        v = find(v);
        return u == v;
    }
    //加入同一集合
    void join(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v)
        {
            return;
        }
        father[v] = u;
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        init();//记得初始化
        for(int i = 0; i < n; i++)
        {
            if(isSame(edges[i][0], edges[i][1]))
                return edges[i];
            else
                join(edges[i][0], edges[i][1]);
        }
        return {};
    }
};

 685. 冗余连接 II - 力扣(LeetCode)

class Solution {
private:
    static const int N = 1010; // 如题:二维数组大小的在3到1000范围内
    int father[N];
    int n; // 边的数量
    // 并查集初始化
    void init() {
        for (int i = 1; i <= n; ++i) {
            father[i] = i;
        }
    }
    // 并查集里寻根的过程
    int find(int u) {
        return u == father[u] ? u : father[u] = find(father[u]);
    }
    // 将v->u 这条边加入并查集
    void join(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return ;
        father[v] = u;
    }
    // 判断 u 和 v是否找到同一个根
    bool same(int u, int v) {
        u = find(u);
        v = find(v);
        return u == v;
    }
    // 在有向图里找到删除的那条边,使其变成树
    vector<int> getRemoveEdge(const vector<vector<int>>& edges) {
        init(); // 初始化并查集
        for (int i = 0; i < n; i++) { // 遍历所有的边
            if (same(edges[i][0], edges[i][1])) { // 构成有向环了,就是要删除的边
                return edges[i];
            }
            join(edges[i][0], edges[i][1]);
        }
        return {};
    }

    // 删一条边之后判断是不是树
    bool isTreeAfterRemoveEdge(const vector<vector<int>>& edges, int deleteEdge) {
        init(); // 初始化并查集
        for (int i = 0; i < n; i++) {
            if (i == deleteEdge) continue;
            if (same(edges[i][0], edges[i][1])) { // 构成有向环了,一定不是树
                return false;
            }
            join(edges[i][0], edges[i][1]);
        }
        return true;
    }
public:

    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
        int inDegree[N] = {0}; // 记录节点入度
        n = edges.size(); // 边的数量
        for (int i = 0; i < n; i++) {
            inDegree[edges[i][1]]++; // 统计入度
        }
        vector<int> vec; // 记录入度为2的边(如果有的话就两条边)
        // 找入度为2的节点所对应的边,注意要倒序,因为优先返回最后出现在二维数组中的答案
        for (int i = n - 1; i >= 0; i--) {
            if (inDegree[edges[i][1]] == 2) {
                vec.push_back(i);
            }
        }
        // 处理图中情况1 和 情况2
        // 如果有入度为2的节点,那么一定是两条边里删一个,看删哪个可以构成树
        if (vec.size() > 0) {
            if (isTreeAfterRemoveEdge(edges, vec[0])) {
                return edges[vec[0]];
            } else {
                return edges[vec[1]];
            }
        }
        // 处理图中情况3
        // 明确没有入度为2的情况,那么一定有有向环,找到构成环的边返回就可以了
        return getRemoveEdge(edges);

    }
};

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

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

相关文章

javaIO

file类 一个File类的对象可以表示一个具体的文件或目录 mkdir 创建单级文件夹 mkdirs 创建多级文件夹 delete 删除一个文件夹时&#xff0c;文件夹里面必须是空的 listfiles 将文件夹的子集放到一个file类型的数组中 输入及输出的概念 输入input 输出output 把jav…

pyinstaller打包多线程pyqt5程序后,报错,反复弹窗等问题

报错1&#xff1a; Traceback (most recent call last): File “MPL.py”, line 502, in File “Lib\site-packages\PyInstaller\hooks\rthooks\pyi_rth_multiprocessing.py”, line 45, in _freeze_support ValueError: not enough values to unpack (expected 2, got 1) 报…

STM32学习笔记(10_3)- 软件I2C读写MPU6050

无人问津也好&#xff0c;技不如人也罢&#xff0c;都应静下心来&#xff0c;去做该做的事。 最近在学STM32&#xff0c;所以也开贴记录一下主要内容&#xff0c;省的过目即忘。视频教程为江科大&#xff08;改名江协科技&#xff09;&#xff0c;网站jiangxiekeji.com 本期开…

分布式之分布式事务详解

分布式事务与实战运用 什么是分布式事务&#xff1f; 业务场景&#xff1a;用户A转账100元给用户B&#xff0c;这个业务比较简单&#xff0c;具体的步骤&#xff1a; 1、用户A的账户先扣除100元 2、再把用户B的账户加100元 如果在同一个数据库中进行&#xff0c;事务可以保证…

C语言之Linux内核回调函数写法(八十九)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

论文阅读,Accelerating the Lattice Boltzmann Method(五)

目录 一、Article:文献出处&#xff08;方便再次搜索&#xff09; &#xff08;1&#xff09;作者 &#xff08;2&#xff09;文献题目 &#xff08;3&#xff09;文献时间 &#xff08;4&#xff09;引用 二、Data:文献数据&#xff08;总结归纳&#xff0c;方便理解&am…

Nginx的反向代理

Nginx的反向代理 location ^~ /aaa {proxy_pass http://192.168.15.78/; } 1. 跨域 2.Nginx 代理服务器缓存 3.Nginx 负载均衡 4. 动静分离 Nginx的跨域 跨源资源共享 (CORS) 是一种机制&#xff0c;它使用额外的 HTTP 标头让用户代理获得访问来自不同来域的服务器上选定资…

LongAdder 和 AtomicLong

有幸看到一篇关于这个讲解 2个类的讲解&#xff0c;自己也归纳总结一下。 一、解析 看源码底层会发现实现机制不一样&#xff0c;当然这个也是必须的 LongAdder 点进去之后会发现&#xff0c;CAS 它是一个CAS的实现类。至于Cell类JVM提供的内置函数 官方说法是&#xff1a;…

Python版【植物大战僵尸 +源码】

文章目录 写在前面&#xff1a;功能实现环境要求怎么玩个性化定义项目演示&#xff1a;源码分享Map地图:Menubar.py主菜单 主函数&#xff1a;项目开源地址 写在前面&#xff1a; 今天给大家推荐一个Gtihub开源项目&#xff1a;PythonPlantsVsZombies&#xff0c;翻译成中就是…

小程序开发调试指南

调试指南 一、Vconsole 一些线上问题需要在真机中进行调试或日志输出&#xff0c;为方便查看前端日志的输出&#xff0c;App 端提供了调试模式, 打开调试模式后面板界面中会显示 vConsole 按钮&#xff0c;点击后可打开手机端 vConsole界面查看日志输出。 1.如何开启 点击小…

JumpServer 堡垒主机

JumpServer 堡垒机帮助企业以更安全的方式管控和登陆各种类型的资产 SSH&#xff1a;Linux/Unix/网络设备等Windows&#xff1a;Web方式连接/原生RDP连接数据库&#xff1a;MySQL、Oracle、SQLServer、PostgreSQL等Kubernetes&#xff1a;连接到K8s集群中的PodsWeb站点&#x…

复现黄金票据

一、搭建环境 搭建域环境可以点击这个查看步骤 在这里面monowall的配置查看 二、实验步骤 拿到域名 拿到SID 使用mimikatz拿到krbtgt用户的哈希 删除票据 也可以使用mimikatz.exe删除票据&#xff0c;命令是kerberos::purge 伪造票据 拿到域控 伪造成功

物联网实战--入门篇之(六)嵌入式-WIFI驱动(ESP8266)

目录 一、WIFI简介 二、基础网络知识 三、思路讲解 四、代码分析 4.1 状态机制 4.2 客户端连接 4.3 应用数据接收处理 4.4 数据发送 4.5 主函数调用 4.6 网络连接ID分配 五、总结 一、WIFI简介 WIFI在我们生活中太常见了&#xff0c;手机电脑都可以用WiFi连接路由器进行上…

MySQL核心命令详解与实战,一文掌握MySQL使用

文章目录 文章简介演示库表创建数据库表选择数据库删除数据库创建表删除表向表中插入数据更新数据删除数据查询数据WHERE 操作符聚合函数LIKE 子句分组 GROUP BY HAVINGORDER BY(排序) 语句LIMIT 操作符 分页查询多表查询-联合查询 UNION 操作符多表查询-连接的使用-JOIN语句编…

从0到1手把手撸码搭建后台管理系统

从0到1手把手撸码搭建后台管理系统 第一章:系统介绍开发目的与过程 要使用 Vue3 搭建后台&#xff0c;你可以按照以下步骤进行&#xff1a; 安装 Vue3&#xff1a;使用包管理工具&#xff08;如 npm 或 yarn&#xff09;安装 Vue3。选择构建工具&#xff1a;选择一个适合的构…

Spring之循环依赖

什么是循环依赖? 依赖的相互引用,如下列的这种形式 Component public class A {Autowiredprivate B b;}Component public class B {Autowiredprivate A a; } Spring是如何解决循环依赖的 Spring是通过三级缓存来解决循环依赖 singletonObjects : 单例bean,已经实例化,完成…

非周期连续函数的傅里叶变换

首先 我们把一个非周期信号扩展成一个周期信号 然后用傅里叶级数展开 也可以得到对应的级数系数 利用周期趋向于无穷大 可以把傅里叶级数展开就变成了一个积分 而神奇的是积分里其实还有一个积分 这样我们就得到了傅里叶变换对 我们把里面的积分成为函数的傅里叶变换 把外面…

C语言交换二进制位的奇数偶数位

基本思路 我们要先把想要交换的数的二进制位给写出来假如交换13的二进制位&#xff0c;13的二进制位是 0000 0000 0000 0000 0000 0000 0000 1101然后写出偶数位的二进制数&#xff08;偶数位是1的&#xff09; 1010 1010 1010 1010 1010 1010 1010 1010然后写出奇数位的二进…

Mac通过Idea启动Tomcat时出现Cannot run program xxx/catalina.sh 错误

问题描述 Mac通过Idea启动Tomcat时出现Cannot run program xxx/catalina.sh错误&#xff0c;详细如下&#xff1a; Error running Tomcat9 Cannot run program "/Users/xxx/Desktop/work/devtools/apache-tomcat-9.0.19/bin/catalina.sh" (in directory "/U…

算法设计课第一周(排序算法的效率分析)

实验1 排序算法的效率分析 一、【实验目的】 &#xff08;1&#xff09;复习排序算法的实现过程&#xff1b; &#xff08;2&#xff09;设计平均与最坏情况下时间复杂度的数据环境并理解相关含义&#xff1b; &#xff08;3&#xff09;初步了解算法时间复杂度的分析方法。…