学校的班级个数【并查集基础应用,Java实现】
题目描述
现有一个学校,学校中有若干个班级,每个班级中有若干个学生,每个学生只会存在于一个班级中。如果学生
A和学生B处于一个班级,学生B和学生C处于一个班级,那么我们称学生A和学生C也处于一个班级。现已知学校中共
n个学生(编号为从1到n),并给出m组学生关系(指定两个学生处于一个班级),问总共有多少个班级。
输入描述
第一行两个整数
n、m(1≤n≤100,1≤m≤100),分别表示学生个数、学生关系个数;接下来
m行,每行两个整数a和b(1≤a≤n,1≤b≤n, a≠b),表示编号为a的学生和编号为b的学生处于一个班级。
输出描述
输出一个整数,表示班级个数。
样例
输入
5 3 // 共5个学生,3对关系
4 2 // 4号学生和2号学生一个班
1 3
2 5
输出
2 // 共两个班
思路分析
- 这种题目第一想法可能是深度遍历的思想,每次从一个未被访问过的点出发走到底,每走到一个节点都标记为已访问,出发的次数即为班级个数。
- 不过这种类型的题目也可以使用并查集来解决,并且效果可能会更好,并查集的基本思路如下👇:
- 设立数组
father,father[son]存放的是son的父亲节点【即是一个整体的】 - 初始
son的父亲节点为它本身,也就是father[son]=son - 当传入一对关系时【如
a与b节点为一个整体】,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实现】
题目描述 现有一个学校,学校中有若干个班级,每个班级中有若干个学生,每个学生只会存在于一个班级中。如果学生A和学生B处于一个班级,学生B和学生C处于一个班级,那么我们称学生A和学生C也处于一个班级。 现已知学校中共…...
WSL2使用Nvidia-Docker实现CUDA版本自由切换
众所周知,深度学习的环境往往非常麻烦,经常不同的项目所依赖的 torch、tensorflow 包对 CUDA 的版本也有不同的要求,Linux 下进行 CUDA 的管理比较麻烦,是一个比较头疼的问题。 随着 WSL2 对物理机显卡的支持,Nvidia-…...
pygame9 扫雷游戏2
一、响应鼠标左键事件 pygame.MOUSEBUTTONDOWN 表示鼠标事件发生, pygame.mouse.get_pressed()[0] 确认是鼠标左键被按下 pygame.mouse.get_pos() 获取到鼠标按下时的坐标值。 因此,我们可以在事件逻辑中例用此三个函数判断鼠标事件及对应的坐标&#x…...
逻辑电路代数运算(上)
逻辑代数L是一个封闭的代数系统,由一个逻辑变量集K,常量0和1,以及与或非三种基本运算构成。 参与逻辑运算的变量叫逻辑变量,用字母A,B……表示。每个变量的取值非0 即1。 0、1不表示数的大小,而是代表两种不…...
Rabbit快速入门
入门案例 需求:使用简单模式完成消息传递 步骤: 创建工程(生成者、消费者) 分别添加依赖 编写生产者发送消息 编写消费者接收消息 3.1.2. 添加依赖 往heima-rabbitmq的pom.xml文件中添加如下依赖: <dependenc…...
【react+ts- forwardRef】
reactts- forwardRef1. 学习资料2. 普通input透传2.1 TS版本2.2 JS版本3. TS-Antd-Form组价透传引用传递(Ref forwading)是一种通过组件向子组件自动传递 引用ref 的技术。对于应用者的大多数组件来说没什么作用。但是对于有些重复使用的组件,…...
计算机网络-- 网络层(day06)
文章目录网络层思维导图IPv4地址的应用规划定长的子网掩码变长的子网掩码VLSMIP数据报的发送和转发过程主机发送IP数据报路由器转发IP数据报静态路由选择动态路由选择路由选择协议概述常见的路由选择协议路由器的基本结构路由信息协议RIP的基本工作原理开放最短路径优先OSPF的基…...
docker 镜像
一、介绍 镜像:是一种轻量级、可执行的独立软件包,它包含运行某个软件所需的所有内容,我们把应用程序和配置依赖打包好形成一个可交付的运行环境(包括代码,运行时需要的库,环境变量和配置文件等)这个打包好的运行环境就是image镜像文件。 只有通过这个镜…...
JUC并发编程与源码分析笔记11-Java对象内存布局和对象头
先从阿里及其它大厂面试题说起 你觉得目前面试,你还有那些方面理解的比较好,我没问到的,我说了juc和jvm以及同步锁机制那先说juc吧,说下aqs的大致流程cas自旋锁,是获取不到锁就一直自旋吗?cas和synchronized区别在哪…...
JavaSE之集合篇
文章目录前言一、集合概述集合继承结构图二、Collection接口中常用方法2.1Collection中存放什么元素?2.2常用方法2.3迭代器三、List接口中常用的方法四、ArrayList初始化容量及扩容五、Vector六、Map接口常用方法七、Properties前言 由于在刷题过程中,经…...
LeetCode分类刷题-----贪心算法
贪心算法贪心455.分发饼干376.摆动序列53.最大子序和122.买卖股票的最佳时机||55.跳跃游戏45.跳跃游戏||1005.K次取反后最大化的数组和134.加油站135.分发糖果860.柠檬水找零406.根据身高重建队列452.用最少数量的箭引爆气球,提供两种解决方案。首先,SiteWhere 的社区版 (CE) 是在 CPAL 许可下提供的。对于此解…...
【unity】rts engine 6 放置并建造建筑;
一 放置并建造建筑 GameManager -> Essential -> BuildingExtension 查看 building placement building position y offset Y轴偏移,建筑离地距离,可0.1 terrain max distance 放置建筑与允许地形的最大距离,可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绘制椭圆形相关系矩阵图
数据/代码准备 数据及代码下载: 下载专区-《MATLAB统计分析与应用:40个案例分析》程序与数据 绘图函数: matrixplot(data, PARAM1,val1, PARAM2,val2, ...) 案例 数据如下: MATLAB代码如下: clc close all clear …...
「SQL面试题库」 No_1 员工薪水中位数
🍅 1、专栏介绍 「SQL面试题库」是由 不是西红柿 发起,全员免费参与的SQL学习活动。我每天发布1道SQL面试真题,从简单到困难,涵盖所有SQL知识点,我敢保证只要做完这100道题,不仅能轻松搞定面试ÿ…...
Python机器学习17——极限学习机(ELM)
本系列基本不讲数学原理,只从代码角度去让读者们利用最简洁的Python代码实现机器学习方法。 背景: 极限学习机(ELM)也是学术界常用的一种机器学习算法,严格来说它应该属于神经网络,应该属于深度学习栏目,但是我这里把它…...
二分查找与判定树
二分查找的算法思想二分查找也称“折半查找”,要求查找表为采用顺序存储结构的有序表。本例一律采用升序排列。二分查找每一次都会比较给定值与序列[low,high]的中间元素,该元素的下标为mid (lowhigh)/2,若两者相等,则返回元素的下标为mid;如…...
反转链表(精美图示详解哦)
全文目录引言反转链表题目描述与思路实现总结引言 在学习了单链表的相关知识后,尝试实现一些题目可以帮助我们更好的理解单链表的结构以及对其的使用。 从这篇文章开始,将会介绍一些编程题来帮助我们更好的掌握单链表: 分别是反转链表、链表…...
第19节 Node.js Express 框架
Express 是一个为Node.js设计的web开发框架,它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用,和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...
Docker 离线安装指南
参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性,不同版本的Docker对内核版本有不同要求。例如,Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本,Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...
剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
如何在最短时间内提升打ctf(web)的水平?
刚刚刷完2遍 bugku 的 web 题,前来答题。 每个人对刷题理解是不同,有的人是看了writeup就等于刷了,有的人是收藏了writeup就等于刷了,有的人是跟着writeup做了一遍就等于刷了,还有的人是独立思考做了一遍就等于刷了。…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
稳定币的深度剖析与展望
一、引言 在当今数字化浪潮席卷全球的时代,加密货币作为一种新兴的金融现象,正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而,加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下,稳定…...
