本文主要是介绍华为od最新算法题(100分题) Linux发行版的数量(Java JS Python),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
Linux操作系统有多个发行版,distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联,例如Ubuntu基于Debian开发,而Mint又基于Ubuntu开发,那么我们认为Mint同Debian也存在关联。
发行版集是一个或多个相关存在关联的操作系统发行版,集合内不包含没有关联的发行版。
给你一个 n * n 的矩阵 isConnected,其中 isConnected[i][j] = 1 表示第 i 个发行版和第 j 个发行版直接关联,而 isConnected[i][j] = 0 表示二者不直接相连。
返回最大的发行版集中发行版的数量。
输入描述
第一行输入发行版的总数量N,
之后每行表示各发行版间是否直接相关
输出描述
输出最大的发行版集中发行版的数量
备注
1 ≤ N ≤ 200
用例
输入 4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
输出 3
说明
Debian(1)和Unbuntu(2)相关
Mint(3)和Ubuntu(2)相关,
EeulerOS(4)和另外三个都不相关,
所以存在两个发行版集,发行版集中发行版的数量分别是3和1,所以输出3。
题目解析
本题可以利用并查集求解,本题要求的就是各个连通分量的节点数,并输出最大的连通分量的节点数。
JavaScript算法源码
/* 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) => {
这篇关于华为od最新算法题(100分题) Linux发行版的数量(Java JS Python)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!