There is an infrastructure of n cities with some number of roads connecting these cities. Each roads[i] = [ai, bi] indicates that there is a bidirectional road between cities ai and bi.
The network rank of two different cities is defined as the total number of directly connected roads to either city. If a road is directly connected to both cities, it is only counted once.
The maximal network rank of the infrastructure is the maximum network rank of all pairs of different cities.
Given the integer n and the array roads, return the maximal network rank of the entire infrastructure.
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.
Constraints:
2 <= n <= 1000 <= roads.length <= n * (n - 1) / 2roads[i].length == 20 <= ai, bi <= n-1ai != biThis approach involves counting the number of roads connected to each city and then checking directly connected pairs to maximize the network rank. For each pair of cities, calculate their combined road count and subtract one if there is a direct road between the two cities since that road is counted twice.
We use an array to store how many roads connect to each city. For two cities, we sum their connections and subtract one if there is a direct road between them, ensuring the road isn't counted twice. We check each possible pair to find the maximal rank.
C++
Time Complexity: O(|E| + n2), where |E| is the number of roads and n is the number of cities.
Space Complexity: O(n), for storing road counts and direct connection set.
This approach utilizes an adjacency matrix to track connections between cities and then computes the maximal network rank by leveraging matrix operations. This can be particularly useful when sparsity is high and offers constant time complexity for checking direct connections.
An adjacency matrix allows quick checks of direct connections between cities. We leverage the matrix to ensure we only count roads once for directly connected city pairs. Each pair of cities is evaluated to find the maximal rank.
C#
Time Complexity: O(n2)
Space Complexity: O(n2), due to the adjacency matrix.
| Approach | Complexity |
|---|---|
| Degree Counting and Direct Road Check | Time Complexity: O(|E| + n2), where |E| is the number of roads and n is the number of cities. |
| Adjacency Matrix Based Calculation | Time Complexity: O(n2) |
maximal network rank | maximal network rank leetcode | leetcode 1615 | graph • Naresh Gupta • 10,913 views views
Watch 9 more video solutions →Practice Maximal Network Rank with our built-in code editor and test cases.
Practice on FleetCode