华为机试 - 城市聚集度
创始人
2024-01-25 04:23:24
0

目录

题目描述

输入描述

输出描述

用例

题目解析

算法源码


题目描述

一张地图上有n个城市,城市和城市之间有且只有一条道路相连:要么直接相连,要么通过其它城市中转相连(可中转一次或多次)。城市与城市之间的道路都不会成环

当切断通往某个城市 i 的所有道路后,地图上将分为多个连通的城市群,设该城市i的聚集度为DPi(Degree of Polymerization),DPi = max(城市群1的城市个数,城市群2的城市个数,…城市群m 的城市个数)。

请找出地图上DP值最小的城市(即找到城市j,使得DPj = min(DP1,DP2 … DPn))

提示:如果有多个城市都满足条件,这些城市都要找出来(可能存在多个解

提示:DPi的计算,可以理解为已知一棵树,删除某个节点后;生成的多个子树,求解多个子数节点数的问题。

输入描述

每个样例:第一行有一个整数N,表示有N个节点。1 <= N <= 1000。

接下来的N-1行每行有两个整数x,y,表示城市x与城市y连接。1 <= x,  y <= N

输出描述

输出城市的编号。如果有多个,按照编号升序输出。

用例

输入5
1 2
2 3
3 4
4 5
输出3
说明

输入表示的是如下地图:

对于城市3,切断通往3的所有道路后,形成2个城市群[(1,2),(4,5)],其聚集度分别都是2。DP3 = 2。

对于城市4,切断通往城市4的所有道路后,形成2个城市群[(1,2,3),(5)],DP4 = max(3,1)= 3。

依次类推,切断其它城市的所有道路后,得到的DP都会大于2,因为城市3就是满足条件的城市,输出是3。

输入6
1 2
2 3
2 4
3 5
3 6
输出2 3
说明将通往2或者3的所有路径切断,最大城市群数量是3,其他任意城市切断后,最大城市群数量都比3大,所以输出2 3

题目解析

用例1的意思如下:

DPi = max(城市群1的城市个数,城市群2的城市个数,…城市群m 的城市个数)

 题目要求找出地图上DP值最小的城市(即找到城市j,使得DPj = min(DP1,DP2 … DPn)),

因此DP3最小,输出DP3的3。

用例2图示如下

输出2,3。

通过上面两个示例的图示可以发现,其实本题就是求解:图的连通分量。

本题的难点在于,分量关系没有直接给出,需要我们自己推导,其次是需要我们统计出每个连通分量的节点个数。

比如,上面且1的所有联系,则会产生两个连通分量,分别是[1], [4,2,3,5,6],这两个连通分量的节点个数分别为1,5。

求解图的连通分量,我们一般使用并查集。

但是,这里我们不能直接根据输入的连接关系,来产生并查集,因为输入的连接关系没有被切断。

本题是要我们尝试切断每一个城市的连接,因此我们遍历出每一个城市,比如城市2,然后遇到和城市2相关的连接后,我们就跳过并查集的合并操作,这样就能产生切断效果。

我们模拟下用例2

初始时,每个城市的父都是自己

输入的连接关系如下
1 2
2 3
2 4
3 5
3 6

现在我们要切断城市2的所有联系,则遇到和2相关的连接时就不进行合并操作

因此上述连接关系只需要考虑
3 5
3 6

这样的话,最终并查集的合并结果为

可以发现,父为3的连通分量具有最多城市数量

这样的话,我们就可以求解出每个DPi了,最后求其中最小的DP对应i即可。

算法源码

/* JavaScript Node ACM模式 控制台输入获取 */
const readline = require("readline");const rl = readline.createInterface({input: process.stdin,output: process.stdout,
});const lines = [];
let n;
rl.on("line", (line) => {lines.push(line);if (lines.length === 1) {n = parseInt(lines[0]);}if (n && lines.length === n) {lines.shift();const relations = lines.map((line) => line.split(" ").map(Number));console.log(getMinDP(relations, n));lines.length = 0;}
});function getMinDP(relations, n) {// min用于保存DPj,即城市聚集度let min = Infinity;// city用于保存j,即城市序号let city = [];// 遍历每个城市 1~nfor (let i = 1; i <= n; i++) {const ufs = new UnionFindSet(n);for (let [x, y] of relations) {// 切断城市的所有道路,即忽略和城市i有联系的合并操作if (x === i || y === i) continue;ufs.union(x, y);}// 统计各个连通分量自身的城市个数const count = {};ufs.fa.forEach((f) => {count[f] ? count[f]++ : (count[f] = 1);});// 取最多城市个数作为当前的切断城市的聚集度const dp = Object.values(count).sort((a, b) => b - a)[0];if (dp < min) {min = dp;city = [i];} else if (dp === min) {city.push(i);}}return city.join(" ");
}/* 并查集 */
class UnionFindSet {constructor(n) {this.fa = new Array(n + 1).fill(0).map((_, idx) => idx);this.count = n;}find(x) {if (x !== this.fa[x]) {return (this.fa[x] = this.find(this.fa[x]));}return x;}union(x, y) {let x_fa = this.find(x);let y_fa = this.find(y);if (x_fa !== y_fa) {this.fa[y_fa] = x_fa;this.count--;}}
}

相关内容

热门资讯

深圳战略性新兴产业和未来产业规... 只要几千元,一台无人机,就可以全新视角俯瞰世界;未来的小城市,也可能会用上“云轨”绿色交通,成为轨道...
中国有潜力的新兴行业 涓浗鏈... 确定不再关注此人吗确定取消文/新浪财经意见领袖专栏作家程实、钱智俊“世界赠我以创伤,而伤口将长出翅膀...
新兴产业基金是否仍有领涨潜力 ... 新兴产业基金是否仍有领涨潜力中国基金报中国基金报记者杨磊新兴产业基金领涨近一年半的时间,未来是否还会...
全国公布首批66个战略性新兴产... 原标题:全国公布首批66个战略性新兴产业集群名单,山东入选数量居首近日,国家发展改革委下发通知,在新...
西安大学生创业贷款最高50万元... 27岁的肖潼杰大学毕业后,和亲戚合伙开办了一家装修公司。日前,他来到西安市就业服务中心,将一整套资料...
妇联网谈:青岛女大学大学生创业... 妇联网谈:青岛女大学生可申请5万无息贷款来源:青岛新闻网作者:谢小真2015-07-字号:A-A+青...
新兴的服务行业有哪些 新兴的服... 2018年,江苏服务业保持总体平稳较快的发展态势,产业规模继续扩张,占GDP比重稳步攀升,内部结构不...
重庆加快发展战略性新兴服务业 ... 重庆商报讯昨日记者从重庆市政府网获悉,市政府办公厅发布《加快发展战略性新兴服务业的实施意见》,提出到...
服务业岗位受青睐 新兴产业技术... □记者原付川3月5日至13日,雄安新区在三县县城及部分乡镇,举办了9场春风行动专场招聘会。记者走访发...
本土创业第一读本孙陶然创业36... 拉卡拉集团董事长孙陶然百万册畅销书《创业36条军规》,近日将由中信出版社再版上市。本次再版,作者孙陶...