Medium · Graphs

Maximal Network Rank

Given n cities labeled 0 to n − 1 and roads where roads[i] = [ai, bi] is a two-way road between ai and bi, return the maximal network rank: over all pairs of different cities, the largest number of roads connected to either city, where a road joining the two cities is counted once.

Examples

Example 1

{
  "adj": [
    [1, 2],
    [0, 2, 3],
    [0, 1],
    [1, 4],
    [3]
  ]
}

Output: max rank 4

Example 2

{
  "adj": [
    [1, 2, 3],
    [0, 2],
    [0, 1, 3],
    [0, 2, 4],
    [3, 5],
    [4]
  ]
}

Output: max rank 5

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.