• Explanation: City 1 and City 3 each have 3 roads connecting to them. The road between City 1 and City 3 is counted only once. So, the maximal network rank is 5.

Example 3:

• Input: n = 3, roads = [[0, 1], [0, 2], [1, 2]]
• Expected Output: 3
• Explanation: City 0 and City 1 each have 2 roads connecting to them. The road between City 1 and City 2 is counted only once. So, the maximal network rank is 3.

Constraints:

• 2 <= n <= 100
• 0 <= roads.length <= n * (n - 1) / 2
• roads[i].length == 2
• 0 <= a_i, b_i <= n-1
• a_i != b_i
• Each pair of cities has at most one road connecting them.

Solution

To solve this problem, we need to calculate the number of roads each city is connected to. Then, for every pair of cities, we sum the number of roads connected to both cities, making sure to not double-count the road directly connecting the two cities (if it exists). We keep track of the maximum network rank encountered during this process.

This approach ensures we efficiently compute the network rank for all city pairs. By leveraging an adjacency list and iterating through the city pairs, we achieve an optimal solution that balances clarity and performance.

Note: This problem uses the finding of the degree of each vertex (city).

Step-by-step Algorithm

To solve this problem:

1. Initialize Data Structures:

   • Create an array degree of size n to store the number of roads connected to each city.
   • Create a set directRoads to store pairs of directly connected cities.

2. Populate Degree and Direct Roads:

   • Loop through each road in the roads array.
   • For each road [a, b], increment the degree of both cities a and b by 1.
   • Add both (a, b) and (b, a) to the directRoads set.

3. Calculate Maximal Network Rank:

   • Initialize a variable maxRank to store the maximum network rank found.
   • Loop through every pair of cities (i, j) where i < j.
   • For each pair, calculate the current network rank as degree[i] + degree[j].
   • If (i, j) is in the directRoads set, decrement the current rank by 1.
   • Update maxRank to be the maximum of maxRank and the current network rank.

4. Return Result:

   • Return maxRank as the result.

Algorithm Walkthrough

Given n = 4 and roads = [[0, 1], [0, 3], [1, 2], [1, 3]]:

1. Initialize Data Structures:

   • degree = [0, 0, 0, 0]
   • directRoads = {}

2. Populate Degree and Direct Roads:

   • For road [0, 1]:

     • Increment degree[0] to 1 and degree[1] to 1.
     • Add (0, 1) and (1, 0) to directRoads.
     • degree = [1, 1, 0, 0]
     • directRoads = {"0,1", "1,0"}

   • For road [0, 3]:

     • Increment degree[0] to 2 and degree[3] to 1.
     • Add (0, 3) and (3, 0) to directRoads.
     • degree = [2, 1, 0, 1]
     • directRoads = {"0,1", "1,0", "0,3", "3,0"}

   • For road [1, 2]:

     • Increment degree[1] to 2 and degree[2] to 1.
     • Add (1, 2) and (2, 1) to directRoads.
     • degree = [2, 2, 1, 1]
     • directRoads = {"0,1", "1,0", "0,3", "3,0", "1,2", "2,1"}

   • For road [1, 3]:

     • Increment degree[1] to 3 and degree[3] to 2.
     • Add (1, 3) and (3, 1) to directRoads.
     • degree = [2, 3, 1, 2]
     • directRoads = {"0,1", "1,0", "0,3", "3,0", "1,2", "2,1", "1,3", "3,1"}

3. Calculate Maximal Network Rank:

   • Initialize maxRank = 0.

   • Compare pairs of cities:

     • For (0, 1):
       • currentRank = degree[0] + degree[1] = 2 + 3 = 5
       • Since (0, 1) is in directRoads, decrement currentRank to 4.
       • Update maxRank to 4.
     • For (0, 2):
       • currentRank = degree[0] + degree[2] = 2 + 1 = 3
       • maxRank remains 4.
     • For (0, 3):
       • currentRank = degree[0] + degree[3] = 2 + 2 = 4
       • Since (0, 3) is in directRoads, decrement currentRank to 3.
       • maxRank remains 4.
     • For (1, 2):
       • currentRank = degree[1] + degree[2] = 3 + 1 = 4
       • Since (1, 2) is in directRoads, decrement currentRank to 3.
       • maxRank remains 4.
     • For (1, 3):
       • currentRank = degree[1] + degree[3] = 3 + 2 = 5
       • Since (1, 3) is in directRoads, decrement currentRank to 4.
       • maxRank remains 4.
     • For (2, 3):
       • currentRank = degree[2] + degree[3] = 1 + 2 = 3
       • maxRank remains 4.

4. Return Result:

   • The result is 4.

Code