张家口网站设计,无锡朝阳网站建设,免费搭建网站模板,月熊志网站题目描述#xff1a;
Linux操作系统有多个发行版#xff0c;distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联#xff0c;例如Ubuntu基于Debian开发#xff0c;而Mint又基于Ubuntu开发#xff0c;那么我们认为Mint同Debian也存在关联。
发行版集是一个或多…题目描述
Linux操作系统有多个发行版distrowatch.com提供了各个发行版的资料。这些发行版互相存在关联例如Ubuntu基于Debian开发而Mint又基于Ubuntu开发那么我们认为Mint同Debian也存在关联。
发行版集是一个或多个相关存在关联的操作系统发行版集合内不包含没有关联的发行版。
给你一个 n x n 的矩阵 isConnected 其中 isConnected[i][j] 1 表示第 i 个发行版和第 j 个发行版直接关联而 isConnected[i][j] 0 表示二者不直接相连。
返回最大的发行版集中发行版的数量
输入描述
第一行输入发行版的总数量N之后每行表示各发行版间是否直接相关
输出描述
输出最大的发行版集中发行版的数量
补充说明
1 N 200收起
示例1
输入
4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1
输出
3
说明
Debian(1)和Ubuntu(2)相关Mint(3)和Ubuntu(2)相关EeulerOS(4)和另外三个都不相关所以存在两个发行版集发行版集中发行版的数量分别是3和1所以输出3public class Linux发行版本 {// n*n的矩阵private static int n;private static int[][] ints;// 用来记录目前版本集中的版号private static SetInteger set;public static void main(String[] args) {// 输入Scanner sc new Scanner(System.in);n sc.nextInt();// 填充初始矩阵ints[][]ints new int[n][n];for (int i 0; i n; i){for (int j 0 ;j n; j){ints[i][j] sc.nextInt();}}// 从当前集合开始已经关联的一个最大的linux版本集合SetInteger temp new HashSetInteger();int max 0;for (int i 0; i n; i){if (!temp.contains(i)){// 已经关联过的则不需要再做处理set new HashSetInteger();handle(i);max Math.max(max, set.size());temp.addAll(set);}}System.out.println(max);}public static void handle(int linux){for (int i linux; i n; i){if (!set.contains(i) ints[linux][i] 1){set.add(i);// 添加到已关联的版本handle(i);}}}
}
