Maximal Network Rank
MediumGraph · Microsoft
There are n cities numbered 0 to n - 1, and roads[i] = [a, b] is an undirected road between cities a and b.
The network rank of two different cities is the number of distinct roads that touch at least one of them. A road directly connecting the two cities is counted only once.
Return the maximum network rank over all pairs of different cities.
Example 1
- Input:
- n = 8, roads = [[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3], [4, 5], [4, 6], [4, 7]]
- Output:
- 6
- Explanation
- Cities 0 to 3 all have 3 roads, but every pair of them is directly connected, so their rank is
3 + 3 - 1 = 5. City 4 also has 3 roads and no road to city 0, so the pair (0, 4) reaches 6.
Example 2
- Input:
- n = 4, roads = [[0, 1], [2, 3]]
- Output:
- 2
- Explanation
- Picking one city from each road, such as 0 and 2, touches both roads for a rank of 2.
Example 3
- Input:
- n = 3, roads = []
- Output:
- 0
- Explanation
- There are no roads, so every pair has rank 0.
Constraints
2 <= n <= 1000 <= roads.length <= n * (n - 1) / 2roads[i].length == 2,0 <= a, b < n,a != b- Each pair of cities has at most one road between them