Sponsored
Sponsored
This 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.
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.
1def maximal_network_rank(n, roads):
2 road_count = [0] * n
3 direct_road = set()
4
5 for a, b in roads:
6 road_count[a] += 1
7 road_count[b] += 1
8 direct_road.add((min(a, b), max(a, b)))
9
10 max_rank = 0
11 for i in range(n):
12 for j in range(i+1, n):
13 rank = road_count[i] + road_count[j]
14 if (i, j) in direct_road:
15 rank -= 1
16 max_rank = max(max_rank, rank)
17 return max_rankWe 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.
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.
Time Complexity: O(n2)
Space Complexity: O(n2), due to the adjacency matrix.
1public class Solution {
2 public int
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.