1615.Maximal Network Rank
===
###### tags: `Medium` `Graph`
[1615. Maximal Network Rank](https://leetcode.com/problems/maximal-network-rank/)
### 題目描述
There is an infrastructure of `n` cities with some number of `roads` connecting these cities. Each `roads[i]` = `[ai, bi]` indicates that there is a bidirectional road between cities `ai` and `bi`.
The **network rank** of **two different cities** is defined as the total number of **directly** connected roads to **either** city. If a road is directly connected to both cities, it is only counted **once**.
The **maximal network rank** of the infrastructure is the **maximum network rank** of all pairs of different cities.
Given the integer `n` and the array `roads`, return *the **maximal network rank** of the entire infrastructure*.
### 範例
**Example 1:**
![](https://assets.leetcode.com/uploads/2020/09/21/ex1.png)
```
Input: n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
Output: 4
Explanation: The network rank of cities 0 and 1 is 4 as there are 4 roads that are connected to either 0 or 1. The road between 0 and 1 is only counted once.
```
**Example 2:**
![](https://assets.leetcode.com/uploads/2020/09/21/ex2.png)
```
Input: n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
Output: 5
Explanation: There are 5 roads that are connected to cities 1 or 2.
```
**Example 3:**
```
Input: n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
Output: 5
Explanation: The network rank of 2 and 5 is 5. Notice that all the cities do not have to be connected.
```
**Constraints**:
* 2 <= `n` <= 100
* 0 <= `roads.length` <= `n * (n - 1) / 2`
* `roads[i].length` == 2
* 0 <= `ai`, `bi` <= n-1
* `ai` != `bi`
* Each pair of cities has **at most one** road connecting them.
### 解答
#### Javascript
```javascript=
function maximalNetworkRank(n, roads) {
const graph = new Array(n).fill(0).map(() => []);
for (const [r1, r2] of roads) {
graph[r1].push(r2);
graph[r2].push(r1);
}
let max = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
let count = graph[i].length + graph[j].length;
if (graph[i].includes(j) || graph[j].includes(i)) {
count--;
}
max = Math.max(max, count);
}
}
return max;
}
```
> [name=Marsgoat][time=18 Aug 2023]
### Reference
[回到題目列表](https://marsgoat.github.io/XNnote/coding/leetcodeEveryDay.html)