连通块中点的数量-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学习手册之Filter和Listener使用方法

《Java学习手册之Filter和Listener使用方法》:本文主要介绍Java学习手册之Filter和Listener使用方法的相关资料,Filter是一种拦截器,可以在请求到达Servl... 目录一、Filter(过滤器)1. Filter 的工作原理2. Filter 的配置与使用二、Listen

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

SpringBoot请求参数接收控制指南分享

《SpringBoot请求参数接收控制指南分享》:本文主要介绍SpringBoot请求参数接收控制指南,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring Boot 请求参数接收控制指南1. 概述2. 有注解时参数接收方式对比3. 无注解时接收参数默认位置

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

Spring Boot 整合 SSE的高级实践(Server-Sent Events)

《SpringBoot整合SSE的高级实践(Server-SentEvents)》SSE(Server-SentEvents)是一种基于HTTP协议的单向通信机制,允许服务器向浏览器持续发送实... 目录1、简述2、Spring Boot 中的SSE实现2.1 添加依赖2.2 实现后端接口2.3 配置超时时

Spring Boot读取配置文件的五种方式小结

《SpringBoot读取配置文件的五种方式小结》SpringBoot提供了灵活多样的方式来读取配置文件,这篇文章为大家介绍了5种常见的读取方式,文中的示例代码简洁易懂,大家可以根据自己的需要进... 目录1. 配置文件位置与加载顺序2. 读取配置文件的方式汇总方式一:使用 @Value 注解读取配置方式二

一文详解Java异常处理你都了解哪些知识

《一文详解Java异常处理你都了解哪些知识》:本文主要介绍Java异常处理的相关资料,包括异常的分类、捕获和处理异常的语法、常见的异常类型以及自定义异常的实现,文中通过代码介绍的非常详细,需要的朋... 目录前言一、什么是异常二、异常的分类2.1 受检异常2.2 非受检异常三、异常处理的语法3.1 try-

Java中的@SneakyThrows注解用法详解

《Java中的@SneakyThrows注解用法详解》:本文主要介绍Java中的@SneakyThrows注解用法的相关资料,Lombok的@SneakyThrows注解简化了Java方法中的异常... 目录前言一、@SneakyThrows 简介1.1 什么是 Lombok?二、@SneakyThrows