华为OD机试- Linux发行版的数量-2022Q4 A卷-Py/Java/JS

Linux操作系统有多个发行版，distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联，例如Ubuntu基于Debian开发，而Mint又基于Ubuntu开发，那么我们认为Mint同Debian也存在关联。

        发行版集是一个或多个相关存在关联的操作系统发行版，集合内不包含没有关联的发行版。给你一个nxn的矩阵 isConnected ，其中isConnected[i][i]=1表示第i个发行版和第j个发行版直接关联，而 isConnected[illi]=0 表示二者不直接相连。

返回最大的发行版集中发行版的数量

输入描述:
第一行输入发行版的总数量N，之后每行表示各发行版间是否直接相关
输出描述:
输出最大的发行版集中发行版的数量
补充说明:
1 <= N <= 200

示例1

输入:
4
1 1 0 0

1 1 1 0

0 1 1 0

0 0 0 1

输出:
3
————————————————

Java 代码

import java.util.Scanner;
import java.util.*;
import java.util.stream.Stream;
import java.util.stream.Collectors;class Main {public static void main(String[] args) {// 处理输入Scanner in = new Scanner(System.in);int n = in.nextInt();int[][] matrix = new int[n][n];for(int i=0; i<n; i++){for(int j=0; j<n; j++){matrix[i][j] = in.nextInt();}}//关联过的linux版本Set<Integer> linux_version = new HashSet<>();    int result = 0;for(int i=0; i<n; i++){if(!linux_version.contains(i)){  //当前版本集Set<Integer> current_version_set = new HashSet<>();check(current_version_set, i, matrix);result = Math.max(result, current_version_set.size()); linux_version.addAll(current_version_set);  }}System.out.println(result);}public static void check(Set<Integer> current_version_set, int n, int[][] matrix){for(int i=0; i<matrix.length; i++){if(current_version_set.contains(i)){    continue;}if(n != i && matrix[n][i] == 1){  current_version_set.add(i);check(current_version_set, i,matrix);}}}}

Python代码

import functools
import collections
import math
from itertools import combinations
from re import match
import copyclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = right#并查集模板
class UF:def __init__(self, n=0):self.count = nself.item = [0 for x in range(n+1)]for i in range(n):self.item[i] = idef find(self, x):if (x != self.item[x]):self.item[x] = self.find(self.item[x])return 0return xdef union_connect(self, x, y):x_item = self.find(x)y_item = self.find(y)if (x_item != y_item):self.item[y_item] = x_itemself.count-=1def check(site_set,n,matrix):for i  in range(len(matrix)):if(i in site_set):    continue        if(n != i and matrix[n][i] == 1):site_set.add(i)check(site_set, i,matrix)#处理输入
N = int(input())
matrix = []
for i in range(N):matrix.append([int(x) for x in input().split(" ")])#关联过的linux版本
site_set = set()  
#需要遍历的次数  
res = 0   
for i in range(N):if(i in site_set):continue#当前版本集temp = set()check(temp, i, matrix)site_set = set.union(site_set, temp)res = max(res, len(temp))print(res)

JS代码

//并查集模板
class UF {constructor(n) {this.count = nthis.item = new Array(n)for(let i=0;i<n;i++) {this.item[i]=i}}find(x) {if (x !== this.item[x]) {return (this.item[x] = this.find(this.item[x]))}return x}union_connect(x, y) {let x_item = this.find(x)let y_item = this.find(y)if (x_item !== y_item) {this.item[y_item] = x_itemthis.count--}}
}function main(matrix) {let uf = new UF(matrix.length);for (let i = 0; i < matrix.length; i++) {for (let j = i + 1; j < matrix.length; j++) {if (matrix[i][j] === 1) {uf.union_connect(i, j);}}}let connected = {};for (let i = 0; i < matrix.length; i++) {let fa = uf.find(i);connected[fa] ? connected[fa]++ : (connected[fa] = 1);}// 返回最大节点数console.log(Math.max(...Object.values(connected)))
}main([[1, 1, 0, 0],[1,1 ,1 ,0],[0 ,1, 1, 0],[0, 0 ,0, 1]])