Maximal Network Rank

Given n cities and undirected roads, assign importance values to cities so that the total importance of all roads is maximized. Pattern focus: Degree. High-degree nodes should receive larger labels to maximize the sum over road endpoints.

Input Format

n = number of cities, roads = undirected edges

Output Format

maximum network rank among all city pairs

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • n, roads must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

n = 4
roads = [[0,1],[0,3],[1,2],[1,3]]

Output:

4

Explanation:

Pair (1,3) has the highest rank.

Example 2:

Input:

n = 5
roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]

Output:

5

Explanation:

The best pair combines high-degree cities.

Loading...
Maximal Network Rank - Graph Fundamentals