题目名称

n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。

两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。

整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。

给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。

示例

输入：n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
输出：4
解释：城市 0 和 1 的网络秩是 4，因为共有 4 条道路与城市 0 或 1 相连。位于 0 和 1 之间的道路只计算一次。

输入：n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
输出：5
解释：共有 5 条道路与城市 1 或 2 相连。

题解

这道题使用枚举的方法

首先根据传入的 roads 参数，统计出每一个城市与其他城市的链接状态，和每一个城市链接城市个数。

然后使用双重遍历的方法，找出链接个数最大的两个城市，并且根据两个城市是否连接，来确定是否减一

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
var maximalNetworkRank = function(n, roads) {
  const connect = new Array(n).fill(0).map(() => new Array(n).fill(false)) // y用来存储 每个城市与其他城市的链接状态
  const degree = new Array(n).fill(0) // 记录当前城市与几个城市链接
  for(let i = 0; i < roads.length; i++) {
    let road = roads[i]
    // 这里主要是设置对应城市的链接状态和链接个数
    connect[road[0]][road[1]] = true
    connect[road[1]][road[0]] = true
    degree[road[0]]++
    degree[road[1]]++
  }
  let max = 0
  for(let i = 0; i < n; i++) {
    for(let j = i + 1; j < n; j++) {
      // 如果这两个城市之间存在链接，说明有一条路是重复的，因此需要减一
      let result = degree[i] + degree[j] - (connect[i][j] ? 1 : 0)
      max = Math.max(max, result)
    }
  }
  return max
};
// 方法二，本质上都是同一中方法
var maximalNetworkRank = function(n, roads) {
  const connect = new Array(n).fill(0).map(() => new Set()) // y用来存储 每个城市与其他城市的链接状态
  for(let i = 0; i < roads.length; i++) {
    let road = roads[i]
    // 这里主要是设置对应城市的链接状态和链接个数
    connect[road[0]].add(road[1])
    connect[road[1]].add(road[0])
  }
  let max = 0
  for(let i = 0; i < n; i++) {
    for(let j = i + 1; j < n; j++) {
      // 如果这两个城市之间存在链接，说明有一条路是重复的，因此需要减一
      let result = connect[i].size + connect[j].size - (connect[i].has(j) ? 1 : 0)
      max = Math.max(max, result)
    }
  }
  return max
};