当前位置: 首页 > 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; 分别是反转链表、链表…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...