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 MaximalNetworkRank(int n, int[][] roads) {
3 int[] roadCount = new int[n];
4 bool[,] adjacencyMatrix = new bool[n, n];
5
foreach (var road in roads) {
int a = road[0], b = road[1];
roadCount[a]++;
roadCount[b]++;
adjacencyMatrix[a, b] = true;
adjacencyMatrix[b, a] = true;
}
int maxRank = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
int rank = roadCount[i] + roadCount[j];
if (adjacencyMatrix[i, j]) {
rank--;
}
maxRank = Math.Max(maxRank, rank);
}
}
return maxRank;
}
}Utilizing an adjacency matrix, each road is quickly verified as direct or indirect. The calculation iterates over each pair for the maximal rank, subtracting for direct roads preventing double counting.