1615. 最大网络秩
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。
示例 1：
输入：n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
输出：4
解释：城市 0 和 1 的网络秩是 4，因为共有 4 条道路与城市 0 或 1 相连。位于 0 和 1 之间的道路只计算一次。
示例 2：
输入：n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
输出：5
解释：共有 5 条道路与城市 1 或 2 相连。
示例 3：
输入：n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
输出：5
解释：2 和 5 的网络秩为 5，注意并非所有的城市都需要连接起来。
提示：
2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= ai, bi <= n-1
ai != bi
每对城市之间 最多只有一条 道路相连解答：
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
// 建立一个长度为n的一维数组degrees，存储城市的度数，其中degrees[i]表示第i个城市的度数
int[] degrees = new int[n];
// 建立一个n x n的布尔型二维数组connected，表示两个城市是否相连。如果connected[i][j]为true，则第i个城市和第j个城市相连，否则不相连
boolean[][] connected = new boolean[n][n];
// 初始化最大网络秩为0
int maxRank = 0;
// 遍历所有道路，更新度数数组和相连状态数组
for (int[] road : roads) {
int city1 = road[0];
int city2 = road[1];
// 第city1个城市的度数加一
degrees[city1]++;
// 第city2个城市的度数加一
degrees[city2]++;
// 将两个城市映射到相连状态数组上，并标记这两个城市是相连的（因为连接关系是双向的）
connected[city1][city2] = true;
connected[city2][city1] = true;
}
// 遍历所有城市对，计算他们的网络秩，并更新最大网络秩
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// 计算第i个城市和第j个城市的网络秩。由于仅考虑直接相连的道路，所以需要累加它们的度数值
int rank = degrees[i] + degrees[j];
// 如果这两个城市之间有一条道路，则需要减去重复计算的度数值
if (connected[i][j]) {
rank--;
}
// 更新最大网络秩
maxRank = Math.max(maxRank, rank);
}
}
return maxRank;
}
}
