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

学校的班级个数【并查集基础应用,Java实现】

题目描述

现有一个学校,学校中有若干个班级,每个班级中有若干个学生,每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级,学生B和学生C处于一个班级,那么我们称学生A和学生C也处于一个班级。

现已知学校中共n个学生(编号为从1n),并给出m组学生关系(指定两个学生处于一个班级),问总共有多少个班级。

输入描述

第一行两个整数n、m(1≤n≤100,1≤m≤100),分别表示学生个数、学生关系个数;

接下来m行,每行两个整数ab(1≤a≤n,1≤b≤n, a≠b),表示编号为a的学生和编号为b的学生处于一个班级。

输出描述

输出一个整数,表示班级个数。

样例

输入

5 3			// 共5个学生,3对关系
4 2			// 4号学生和2号学生一个班
1 3
2 5

输出

2		// 共两个班

思路分析

  • 这种题目第一想法可能是深度遍历的思想,每次从一个未被访问过的点出发走到底,每走到一个节点都标记为已访问,出发的次数即为班级个数。
  • 不过这种类型的题目也可以使用并查集来解决,并且效果可能会更好,并查集的基本思路如下👇:
    1. 设立数组fatherfather[son]存放的是son的父亲节点【即是一个整体的】
    2. 初始son的父亲节点为它本身,也就是father[son]=son
    3. 当传入一对关系时【如ab节点为一个整体】,a的父亲就会由b的父亲来担任【共享父亲,b的父亲由a的父亲担任也无妨】,从而使得独立的两个小整体融合为一个大整体,这个操作我们称之为Union
  • 此题只需要顺着并查集的基本思路,设立数组father将父子关系进行存储即可,最后统计father[i]==i的节点数即为班级个数

代码实现

package homework;import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// n 个学生int n = scanner.nextInt();int father[] = new int[n];for (int i = 0; i < n; i++) {father[i] = i;}// m 组关系int m = scanner.nextInt();for (int i = 0; i < m; i++) {// 减1是为了使得编号与数组下标对应上int a = scanner.nextInt() - 1;int b = scanner.nextInt() - 1;// a 与 b 融合为一个整体Union(father, a, b);}int sum = 0;for (int i = 0; i < n; i++) {if (father[i] == i) {sum++;}}System.out.println(sum);}// 寻找下标 son 的父亲节点public static int FindFather(int father[], int son) {if (father[son] == son) {// 自己是自己的爸爸return son;}// 找到son真正的爸爸,并赋值回来【这是个剪枝操作,可以提高查找效率】father[son] = FindFather(father, father[son]);return father[son];}public static void Union(int arr[], int a, int b) {int fatherA = FindFather(arr, a);int fatherB = FindFather(arr, b);// 两个人的爸爸不同,把其中一个的爸爸进行赋值if (fatherA != fatherB) {arr[fatherA] = fatherB;}}}

相关文章:

学校的班级个数【并查集基础应用,Java实现】

题目描述 现有一个学校&#xff0c;学校中有若干个班级&#xff0c;每个班级中有若干个学生&#xff0c;每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级&#xff0c;学生B和学生C处于一个班级&#xff0c;那么我们称学生A和学生C也处于一个班级。 现已知学校中共…...

WSL2使用Nvidia-Docker实现CUDA版本自由切换

众所周知&#xff0c;深度学习的环境往往非常麻烦&#xff0c;经常不同的项目所依赖的 torch、tensorflow 包对 CUDA 的版本也有不同的要求&#xff0c;Linux 下进行 CUDA 的管理比较麻烦&#xff0c;是一个比较头疼的问题。 随着 WSL2 对物理机显卡的支持&#xff0c;Nvidia-…...

pygame9 扫雷游戏2

一、响应鼠标左键事件 pygame.MOUSEBUTTONDOWN 表示鼠标事件发生&#xff0c; pygame.mouse.get_pressed()[0] 确认是鼠标左键被按下 pygame.mouse.get_pos() 获取到鼠标按下时的坐标值。 因此&#xff0c;我们可以在事件逻辑中例用此三个函数判断鼠标事件及对应的坐标&#x…...

逻辑电路代数运算(上)

逻辑代数L是一个封闭的代数系统&#xff0c;由一个逻辑变量集K&#xff0c;常量0和1&#xff0c;以及与或非三种基本运算构成。 参与逻辑运算的变量叫逻辑变量&#xff0c;用字母A&#xff0c;B……表示。每个变量的取值非0 即1。 0、1不表示数的大小&#xff0c;而是代表两种不…...

Rabbit快速入门

入门案例 需求&#xff1a;使用简单模式完成消息传递 步骤&#xff1a; 创建工程&#xff08;生成者、消费者&#xff09; 分别添加依赖 编写生产者发送消息 编写消费者接收消息 3.1.2. 添加依赖 往heima-rabbitmq的pom.xml文件中添加如下依赖&#xff1a; <dependenc…...

【react+ts- forwardRef】

reactts- forwardRef1. 学习资料2. 普通input透传2.1 TS版本2.2 JS版本3. TS-Antd-Form组价透传引用传递&#xff08;Ref forwading&#xff09;是一种通过组件向子组件自动传递 引用ref 的技术。对于应用者的大多数组件来说没什么作用。但是对于有些重复使用的组件&#xff0c…...

计算机网络-- 网络层(day06)

文章目录网络层思维导图IPv4地址的应用规划定长的子网掩码变长的子网掩码VLSMIP数据报的发送和转发过程主机发送IP数据报路由器转发IP数据报静态路由选择动态路由选择路由选择协议概述常见的路由选择协议路由器的基本结构路由信息协议RIP的基本工作原理开放最短路径优先OSPF的基…...

docker 镜像

一、介绍 镜像:是一种轻量级、可执行的独立软件包,它包含运行某个软件所需的所有内容,我们把应用程序和配置依赖打包好形成一个可交付的运行环境(包括代码,运行时需要的库,环境变量和配置文件等)这个打包好的运行环境就是image镜像文件。 只有通过这个镜…...

JUC并发编程与源码分析笔记11-Java对象内存布局和对象头

先从阿里及其它大厂面试题说起 你觉得目前面试&#xff0c;你还有那些方面理解的比较好&#xff0c;我没问到的&#xff0c;我说了juc和jvm以及同步锁机制那先说juc吧&#xff0c;说下aqs的大致流程cas自旋锁&#xff0c;是获取不到锁就一直自旋吗?cas和synchronized区别在哪…...

JavaSE之集合篇

文章目录前言一、集合概述集合继承结构图二、Collection接口中常用方法2.1Collection中存放什么元素&#xff1f;2.2常用方法2.3迭代器三、List接口中常用的方法四、ArrayList初始化容量及扩容五、Vector六、Map接口常用方法七、Properties前言 由于在刷题过程中&#xff0c;经…...

LeetCode分类刷题-----贪心算法

贪心算法贪心455.分发饼干376.摆动序列53.最大子序和122.买卖股票的最佳时机||55.跳跃游戏45.跳跃游戏||1005.K次取反后最大化的数组和134.加油站135.分发糖果860.柠檬水找零406.根据身高重建队列452.用最少数量的箭引爆气球![在这里插入图片描述](https://img-blog.csdnimg.cn…...

SiteWhere开源物联网平台支持意大利都灵智能计量

这篇简短的文章描述了一个基于 SiteWhere 开源物联网平台的智慧城市用例。 SiteWhere总部位于佐治亚州亚特兰大&#xff0c;是一个开源物联网应用程序支持平台 (AEP)&#xff0c;提供两种解决方案。首先&#xff0c;SiteWhere 的社区版 (CE) 是在 CPAL 许可下提供的。对于此解…...

【unity】rts engine 6 放置并建造建筑;

一 放置并建造建筑 GameManager -> Essential -> BuildingExtension 查看 building placement building position y offset Y轴偏移&#xff0c;建筑离地距离&#xff0c;可0.1 terrain max distance 放置建筑与允许地形的最大距离&#xff0c;可1 placable terrain …...

华为OD机试题 - 任务调度(JavaScript)| 含思路

更多题库,搜索引擎搜 梦想橡皮擦华为OD 👑👑👑 更多华为OD题库,搜 梦想橡皮擦 华为OD 👑👑👑 更多华为机考题库,搜 梦想橡皮擦华为OD 👑👑👑 华为OD机试题 最近更新的博客使用说明本篇题解: 任务调度题目输入输出描述示例一输入输出Code解题思路华为OD其…...

《Spring源码深度分析》第4章 自定义标签的解析

目录标题前言一、自定义标签使用二、自定义标签解析1、代码入口2、parseCustomElement【BeanDefinitionParserDelegate】2.1 resolve【DefaultNamespaceHandlerResolver】3、parse【NamespaceHandlerSupport】4、parse【AbstractBeanDefinitionParser】4.1 parseInternal【Abst…...

MATLAB绘制椭圆形相关系矩阵图

数据/代码准备 数据及代码下载&#xff1a; 下载专区-《MATLAB统计分析与应用&#xff1a;40个案例分析》程序与数据 绘图函数&#xff1a; matrixplot(data, PARAM1,val1, PARAM2,val2, ...) 案例 数据如下&#xff1a; MATLAB代码如下&#xff1a; clc close all clear …...

「SQL面试题库」 No_1 员工薪水中位数

&#x1f345; 1、专栏介绍 「SQL面试题库」是由 不是西红柿 发起&#xff0c;全员免费参与的SQL学习活动。我每天发布1道SQL面试真题&#xff0c;从简单到困难&#xff0c;涵盖所有SQL知识点&#xff0c;我敢保证只要做完这100道题&#xff0c;不仅能轻松搞定面试&#xff…...

Python机器学习17——极限学习机(ELM)

本系列基本不讲数学原理&#xff0c;只从代码角度去让读者们利用最简洁的Python代码实现机器学习方法。 背景&#xff1a; 极限学习机(ELM)也是学术界常用的一种机器学习算法&#xff0c;严格来说它应该属于神经网络&#xff0c;应该属于深度学习栏目&#xff0c;但是我这里把它…...

二分查找与判定树

二分查找的算法思想二分查找也称“折半查找”&#xff0c;要求查找表为采用顺序存储结构的有序表。本例一律采用升序排列。二分查找每一次都会比较给定值与序列[low,high]的中间元素&#xff0c;该元素的下标为mid (lowhigh)/2,若两者相等&#xff0c;则返回元素的下标为mid;如…...

反转链表(精美图示详解哦)

全文目录引言反转链表题目描述与思路实现总结引言 在学习了单链表的相关知识后&#xff0c;尝试实现一些题目可以帮助我们更好的理解单链表的结构以及对其的使用。 从这篇文章开始&#xff0c;将会介绍一些编程题来帮助我们更好的掌握单链表&#xff1a; 分别是反转链表、链表…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

测试markdown--肇兴

day1&#xff1a; 1、去程&#xff1a;7:04 --11:32高铁 高铁右转上售票大厅2楼&#xff0c;穿过候车厅下一楼&#xff0c;上大巴车 &#xffe5;10/人 **2、到达&#xff1a;**12点多到达寨子&#xff0c;买门票&#xff0c;美团/抖音&#xff1a;&#xffe5;78人 3、中饭&a…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

【Java学习笔记】BigInteger 和 BigDecimal 类

BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点&#xff1a;传参类型必须是类对象 一、BigInteger 1. 作用&#xff1a;适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

JS设计模式(4):观察者模式

JS设计模式(4):观察者模式 一、引入 在开发中&#xff0c;我们经常会遇到这样的场景&#xff1a;一个对象的状态变化需要自动通知其他对象&#xff0c;比如&#xff1a; 电商平台中&#xff0c;商品库存变化时需要通知所有订阅该商品的用户&#xff1b;新闻网站中&#xff0…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...