#1615
Maximal Network Rank
specialist · 635 · lc medium +30 · verified · 65.9% accepted · 2,446 likes · top 71%
Description
There are n cities and some bidirectional roads. The network rank of two distinct cities equals the total roads connected to either one, counting any direct road between them only once. Return the maximum network rank across all city pairs.
Example 1:
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:
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.
Code
1
2
3