华为od-C卷200分题目2 - 找城市

华为od-C卷200分题目2 - 找城市

题目描述

一个城市规划问题,一个地图有很多城市,两个城市之间只有一种路径,切断通往一
个城市i的所有路径之后,其他的城市形成了独立的城市群,这些城市群里最大的城
市数量,就是聚集度DPi,现在给出一个地图上各个城市的路径,输出聚集度最小的
城市,如果有多个结果,按照编号从小到大输入描述
第一行输入 城市节点数目N
后面N-1输入城市之间的路径输出描述
聚集度最小的城市示例
输入
5
1 2
2 3
3 4
4 5
输出
3
说明
将通往3的所有路径切断,最大城市群数量是2,其他任意城市切断后,最大城市群
数量都比2大,所以输出3
1
输入
6
1 2
2 3
2 4
3 5
3 6
输出
2 3
说明
将通往2或者3的所有路径切断,最大城市群数量是3,其他任意城市切断后,最大
城市群数量都比3大,所以输出2 
import java.util.*;public class Main {static HashMap<Integer, List<Integer>> map;public static void main(String[] args) {int n, a, b;Scanner sc = new Scanner(System.in);n = sc.nextInt();int[] nums = new int[n + 1];map = new HashMap<>();for (int i = 1; i < n; i++) {a = sc.nextInt();b = sc.nextInt();save(a, b);save(b, a);}int max = Integer.MAX_VALUE;TreeSet<Integer> result = new TreeSet<>();HashSet<Integer> set = new HashSet<>();for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {Integer key = entry.getKey();set.add(key);for (Integer i : entry.getValue()) {nums[key] = Math.max(nums[key], dfs(i, set));}if (nums[key] < max) {result.clear();result.add(entry.getKey());max = nums[key];}else if (nums[key] == max) {result.add(entry.getKey());}set.clear();}for (Integer i : result) {System.out.printf(i + " ");}System.out.println();}public static void save(int a, int b) {if (map.containsKey(a)) {map.get(a).add(b);} else {LinkedList<Integer> list = new LinkedList<>();list.add(b);map.put(a, list);}}public static int dfs(int i, HashSet<Integer> set) {Stack<Integer> stack = new Stack<>();int sum = 0;stack.push(i);while (!stack.isEmpty()) {sum++;Integer pop = stack.pop();set.add(pop);for (Integer temp : map.get(pop)) {if (!set.contains(temp)) {stack.push(temp);}}}return sum;}
}

思路:以每个点进行dfs,求子节点的所以路线,求出最大值,然后再求出每个点的最大值找最小值。
在这里插入图片描述
图中以根节点的每个子节点j进行dfs,得到根节点的值为5

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/357950.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

QML 列表,图片展示(一)

文章目录 1.QML 列表&#xff0c;图片展示效果图2.项目基本说明3.项目详解3.1界面显示部分3.2 网络部分 4.源代码5.flickr图片查询链接&#xff0c;后面我们将调整代码&#xff0c;获取更多图片 1.QML 列表&#xff0c;图片展示效果图 2.项目基本说明 该项目来自Qt示例程序 Ph…

2025秋招NLP算法面试真题(二)-史上最全Transformer面试题:灵魂20问帮你彻底搞定Transformer

简单介绍 之前的20个问题的文章在这里&#xff1a; https://zhuanlan.zhihu.com/p/148656446 其实这20个问题不是让大家背答案&#xff0c;而是为了帮助大家梳理 transformer的相关知识点&#xff0c;所以你注意看会发现我的问题也是有某种顺序的。 本文涉及到的代码可以在…

很冷门但真的有趣的IOS应用

Tuesday Tuesday纪念日小组件是一款功能丰富的倒数日和桌面小组件工具APP。此外&#xff0c;Tuesday软件还具有超萌小清新的风格&#xff0c;界面设计清新可爱&#xff0c;适合各种场景使用。用户可以通过小组件实现各种趣味功能&#xff0c;满足不同心情需求。 SideNotes Si…

3d隐藏模型为什么就不见了?---模大狮模型网

在3D建模和设计过程中&#xff0c;经常会遇到需要隐藏某些模型的情况。然而&#xff0c;有时候隐藏之后再也找不到这些模型了。这种情况可能让人感到困惑和沮丧。本文将探讨3D隐藏模型后“消失”的原因&#xff0c;并提供一些解决方法&#xff0c;帮助您更好地管理和查找隐藏的…

ES 8.14 向量搜索优化

参考&#xff1a;https://blog.csdn.net/UbuntuTouch/article/details/139502650 检索器&#xff08;standard、kNN 和 RRF&#xff09; 检索器&#xff08;retrievers&#xff09;是搜索 API 中的一种新抽象概念&#xff0c;用于描述如何检索一组顶级文档。检索器被设计为可以…

Java基础学习-数组

目录 数组定义 注意点&#xff1a; 地址值是数组在内存中实际存储的地址。 案例遍历&#xff1a;遍历数组得到每一个元素&#xff0c;求数组里面所有数据和 案例&#xff1a;定义数组&#xff0c;遍历能被3整除的数字 案例&#xff1a;遍历一个数组&#xff0c;奇数将当前…

docker搭建mongo分片集群

1、mongo分片集群 MongoDB分片集群是一种可扩展的数据库架构&#xff0c;用于处理大量数据和高并发访问。它将数据分成多个分片&#xff0c;并将这些分片分布在多个服务器上&#xff0c;从而实现数据的平衡存储和并行处理 。 通过使用MongoDB的分片集&#xff0c;可以实现数据…

艺体培训机构管理系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;管理员管理&#xff0c;教师管理&#xff0c;学员管理&#xff0c;活动管理&#xff0c;课程管理&#xff0c;选课信息管理 前台账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;论…

Spring Boot+vue社区养老系统(智慧养老平台)

使用技术&#xff1a; springbootvueMySQL 主要功能&#xff1a; 管理员 登录个人资料密码管理, 用户管理:床位类型管理,床位管理,护工管理,老人管理 咨询登记管理&#xff0c;预约登记管理,老人健康信 息管理,费用管理等功能.护工角色包含以下功能: 护工登录&#xff0c;个…

数据库精选题(二)(引言+关系代数)

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;数据库 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 目录 前言 常见概念 一、什么是数据库&#xf…

查找和排序

目录 一、查找 1.1查找的基本概念 1.2顺序查找 1.3折半查找&#xff08;二分查找&#xff09; 1.4散列表的查找 1.4.1基本概念 1.4.2散列函数的构造方法 1.4.3解决冲突的方法 二、排序 2.1排序的基本概念 2.2插入排序 2.2.1直接插入排序&#xff1a; 2.2.2希尔排序…

C++回溯算法(2)

棋盘问题 #include<bits/stdc.h> using namespace std; void func(int,int); bool tf(int,int); void c(); int n,k; char a[110][110]; int cnt20; int main() {cin>>n>>k;for(int i0;i<n;i){for(int j0;j<n;j){cin>>a[i][j];}}func(0,0);cout…

北京BJ90升级新款迈巴赫大连屏四座头等舱行政四座马鞍

北京BJ90升级奔驰迈巴赫头等舱行政四座大联屏的内饰效果会非常出色&#xff0c;将为车辆带来更豪华、高端的内饰氛围。以下是升级后可能的效果&#xff1a; • 科技感提升&#xff1a;奔驰的中控系统一直以来都以其先进的科技和用户友好的界面而闻名。升级后&#xff0c;北京B…

EndNote 21 for Mac v21.3 文献管理软件安装

Mac分享吧 文章目录 效果一、下载软件二、开始安装1、双击运行安装EndNote212、升级 三、运行1、打开软件&#xff0c;测试 安装完成&#xff01;&#xff01;&#xff01;四、注意事项 效果 一、下载软件 下载软件 链接&#xff1a;http://www.macfxb.cn 二、开始安装 1、双击…

深信服科技:2023网络钓鱼趋势分析报告

随着互联网的快速发展和广泛应用&#xff0c;网络钓鱼活动带来的安全隐患愈演愈烈。因应威胁发展&#xff0c;我 们编撰了此份分析报告&#xff0c;旨在全面了解其发展态势&#xff0c;并提醒相关部门、企业和公众加强防范。 在本报告中&#xff0c;我们将详细梳理网络钓鱼的近…

编程精粹—— Microsoft 编写优质无错 C 程序秘诀 07:编码中的假象

这是一本老书&#xff0c;作者 Steve Maguire 在微软工作期间写了这本书&#xff0c;英文版于 1993 年发布。2013 年推出了 20 周年纪念第二版。我们看到的标题是中译版名字&#xff0c;英文版的名字是《Writing Clean Code ─── Microsoft’s Techniques for Developing》&a…

USB - USB在消费领域的应用

Switching in USB Consumer Applications 通用串行总线&#xff08;USB&#xff09;已成为满足终端设备之间日益增长的快速数据传输需求的主流接口--例如&#xff0c;在个人电脑和便携式设备&#xff08;如手机、数码相机和个人媒体播放器&#xff09;之间下载和上传数据。 The…

动手学深度学习(Pytorch版)代码实践 -计算机视觉-37微调

37微调 import os import torch import torchvision from torch import nn import liliPytorch as lp import matplotlib.pyplot as plt from d2l import torch as d2l# 获取数据集 d2l.DATA_HUB[hotdog] (d2l.DATA_URL hotdog.zip,fba480ffa8aa7e0febbb511d181409f899b9baa5…

已解决javax.management.BadStringOperationException异常的正确解决方法,亲测有效!!!

已解决javax.management.BadStringOperationException异常的正确解决方法&#xff0c;亲测有效&#xff01;&#xff01;&#xff01; 目录 问题分析 出现问题的场景 报错原因 解决思路 解决方法 分析错误日志 检查字符串值合法性 确认字符串格式 优化代码逻辑 增加…

pcl::PointXYZRGBA造成点云无法显示

如果pcd文件没有rgba信息&#xff0c;使用pcl::PointXYZRGBA类型打开会提示以下信息&#xff1a; Failed to find match for field rgba另外&#xff0c;显示出来的点云是黑色&#xff0c;如果使用默认背景色为黑色&#xff0c;就无法显示点云了。 如果设置其它背景色&#xf…