连通块中点的数量-java

2024-06-01 09:44
文章标签 java 数量 中点 连通

本文主要是介绍连通块中点的数量-java,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本次我们通过连通块中点的数量来加深我们对并查集的基本操作和原理,并且知道如何在并查集中添加附属信息。

目录

前言☀

一、连通块中点的数量☀

二、算法思路☀

1.无向图🌙

2.在a b之间连一条边,a b可能相等🌙

3.询问a和b是否在一个连通块中,a和b可能相等🌙

4.询问点所在连通块中点的数量🌙

三、代码如下☀

1.代码如下:🌙

2.读入数据🌙

3.代码运行结果🌙

4.代码样例解释🌙

总结☀


前言☀

本次我们通过连通块中点的数量来加深我们对并查集的基本操作和原理,并且知道如何在并查集中添加附属信息。


提示:以下是本篇文章正文内容,下面案例可供参考

一、连通块中点的数量☀

给定一个包含 n 个点(编号为 1∼n)的无向图,初始时图中没有边。

现在要进行 m个操作,操作共有三种:

  1. C a b,在点 a 和点 b 之间连一条边,a 和 b可能相等;
  2. Q1 a b,询问点 a 和点 b是否在同一个连通块中,a 和 b 可能相等;
  3. Q2 a,询问点 a所在连通块中点的数量;

输入格式

第一行输入整数 n 和 m。

接下来 m 行,每行包含一个操作指令,指令为 C a bQ1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b,如果 a 和 b在同一个连通块中,则输出 Yes,否则输出 No

对于每个询问指令 Q2 a,输出一个整数表示点 a 所在连通块中点的数量

每个结果占一行。

数据范围

1≤n,m≤100000

二、算法思路☀

1.无向图🌙

图1.1无向图示例

我们有各种各样的点,然后通过一条边进行连接,且这条边没有方向,例如A与B之间有条边,那么A可以到达B,B也可以到达A;图1.1就是一个无向图。

我们还是引入一个一维整型数组p来存储各个结点的父结点的编号,p数组的索引就表示哪个结点。在这道题中我们还需要引入一个一维整型数组size,用来记录每个集合内结点的个数即我们题上说的连通块内点的个数;规定只有根节点的size数组内的值是有效的

        for(int i = 1;i <= n;i++){p[i] = i;size[i] = 1;}

 这道题跟并查集类似,我们还是需要一个find方法来找到结点x所在集合的根节点的编号。

    public static int find(int x){if(p[x] == x){return x;}return p[x] = find(p[x]);}

对于上述find方法代码如果不太理解的,可以去看我之前写的合并集合的博客(https://blog.csdn.net/m0_63267251/article/details/139294176)里面,里面有详细的解释。

2.在a b之间连一条边,a b可能相等🌙

 图2.1添加边样例图

在这道题中我们往两个点中添加边,a和b如果相等,那么就是一个点自连如图2.1右边所示。还有可能两个点之间已经右边,然后有重复添加了一条边。

图2.2size数组维护 

 我们要添加边,其实就相当于我们把两个集合给合并了一样,例如我们在a和b两个点添加一条边,其实就是将a和b所在的两个集合合并,那么我们只需要找到b所在集合的根节点,然后让b所在集合根节点的父结点变成a所在集合的根节点就完成了合并操作即p[find(b)] = find(a);

 我们还有一个很重要的操作需要维护size数组里面的值,因为我们相当于把b所在集合放到了a所在集合的下面,那么我们只需要将所在a结点集合结点个数加上b所在集合对应的结点个数即可,我们规定了只有根节点的size值是有效的,那么我们只需要 size[find(a)] += size[find(b)]就可完成上述操作。

当然如果a结点和b结点在同一个集合的话,我们就不需要进行size数组的维护了,中间加一个判断。‘

                if(cmd.equals("C")){a = sc.nextInt();b = sc.nextInt();//当a和b已经在一个集中当中,就不需要再改变对应根节点的size值了,不在进行后续size        数组值的更新和根节点值得改变if(find(a) == find(b)){continue;}size[find(a)] += size[find(b)];p[find(b)] = find(a);

3.询问a和b是否在一个连通块中,a和b可能相等🌙

图3.1连通块示例 

 判断两个点是不是在一个连通图中,即a可以到达b,b也可以到达a,就说明两个点是在一个连通图中。如上图3.1中圈起来的就是一个连通图。

我们只需要判断一下结点a所在集合的根节点的值和结点b所在集合的根节点的值是否相等就可判断出是否在同一个连通块中。

    find(a) == find(b) ? "Yes":"No"

4.询问点所在连通块中点的数量🌙

图4.1示例图 

如图4.1所示我们可以看到点1的连通块中有3个点,点4所在的连通块中的点的数量是1。

这里我们只需要返回对应点所在集合的根节点的size数组值就是集合所在连通块中点的个数

    size[find(a)]

三、代码如下☀

1.代码如下:🌙


import java.util.*;
import java.io.*;
public class Main {static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static int N = 100010;static int[] p = new int[N];//用来记录对应结点的集合内所有点的个数static int[] size = new int[N];public static void main(String[] args)throws Exception {Scanner sc = new Scanner(br);int n = sc.nextInt();for(int i = 1;i <= n;i++){p[i] = i;size[i] = 1;}int m = sc.nextInt();while (m-- > 0){String cmd = sc.next();int a,b;if(cmd.equals("C")){a = sc.nextInt();b = sc.nextInt();//当a和b已经在一个集中当中,就不需要再改变对应根节点的size值了if(find(a) == find(b)){continue;}size[find(a)] += size[find(b)];p[find(b)] = find(a);} else if (cmd.equals("Q1")) {a = sc.nextInt();b = sc.nextInt();pw.println(find(a) == find(b) ? "Yes":"No");} else if (cmd.equals("Q2")) {a = sc.nextInt();pw.println(size[find(a)]);}}pw.flush();}public static int find(int x){if(p[x] == x){return x;}return p[x] = find(p[x]);}}

2.读入数据🌙

5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

3.代码运行结果🌙

Yes
2
3

4.代码样例解释🌙

C 1 2 后1和2在同一个集合;Q1 1 2查询1和2是否在同一个集合打印Yes;Q2 1查询1所在集合点的个数为2;C 2 5 将2和5想连,那么1 2 5在同一个集合;Q2 5查询5所在集合点的个数为3。


总结☀

上述通过连通块中点的数量这道题又训练了一遍并查集的基本操作,本质和并查集的代码并无差别,只是我们在并查集的操作过程中可以加入一些维护信息。

这篇关于连通块中点的数量-java的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1020654

相关文章

Java编译生成多个.class文件的原理和作用

《Java编译生成多个.class文件的原理和作用》作为一名经验丰富的开发者,在Java项目中执行编译后,可能会发现一个.java源文件有时会产生多个.class文件,从技术实现层面详细剖析这一现象... 目录一、内部类机制与.class文件生成成员内部类(常规内部类)局部内部类(方法内部类)匿名内部类二、

SpringBoot实现数据库读写分离的3种方法小结

《SpringBoot实现数据库读写分离的3种方法小结》为了提高系统的读写性能和可用性,读写分离是一种经典的数据库架构模式,在SpringBoot应用中,有多种方式可以实现数据库读写分离,本文将介绍三... 目录一、数据库读写分离概述二、方案一:基于AbstractRoutingDataSource实现动态

Springboot @Autowired和@Resource的区别解析

《Springboot@Autowired和@Resource的区别解析》@Resource是JDK提供的注解,只是Spring在实现上提供了这个注解的功能支持,本文给大家介绍Springboot@... 目录【一】定义【1】@Autowired【2】@Resource【二】区别【1】包含的属性不同【2】@

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

Elasticsearch 在 Java 中的使用教程

《Elasticsearch在Java中的使用教程》Elasticsearch是一个分布式搜索和分析引擎,基于ApacheLucene构建,能够实现实时数据的存储、搜索、和分析,它广泛应用于全文... 目录1. Elasticsearch 简介2. 环境准备2.1 安装 Elasticsearch2.2 J

Java中的String.valueOf()和toString()方法区别小结

《Java中的String.valueOf()和toString()方法区别小结》字符串操作是开发者日常编程任务中不可或缺的一部分,转换为字符串是一种常见需求,其中最常见的就是String.value... 目录String.valueOf()方法方法定义方法实现使用示例使用场景toString()方法方法

Java中List的contains()方法的使用小结

《Java中List的contains()方法的使用小结》List的contains()方法用于检查列表中是否包含指定的元素,借助equals()方法进行判断,下面就来介绍Java中List的c... 目录详细展开1. 方法签名2. 工作原理3. 使用示例4. 注意事项总结结论:List 的 contain

Java实现文件图片的预览和下载功能

《Java实现文件图片的预览和下载功能》这篇文章主要为大家详细介绍了如何使用Java实现文件图片的预览和下载功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... Java实现文件(图片)的预览和下载 @ApiOperation("访问文件") @GetMapping("

Spring Boot + MyBatis Plus 高效开发实战从入门到进阶优化(推荐)

《SpringBoot+MyBatisPlus高效开发实战从入门到进阶优化(推荐)》本文将详细介绍SpringBoot+MyBatisPlus的完整开发流程,并深入剖析分页查询、批量操作、动... 目录Spring Boot + MyBATis Plus 高效开发实战:从入门到进阶优化1. MyBatis