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.
1#include <vector>
2#include <unordered_set>
3#include <algorithm>
4using namespace std;
5
6int maximalNetworkRank(int n, vector<vector<int>>& roads) {
7 vector<int> degree(n, 0);
8 unordered_set<int> direct;
9
10 for (auto& road : roads) {
11 int a = road[0], b = road[1];
12 degree[a]++;
13 degree[b]++;
14 direct.insert(min(a, b) * n + max(a, b));
15 }
16
17 int max_rank = 0;
18 for (int i = 0; i < n; ++i) {
19 for (int j = i + 1; j < n; ++j) {
20 int rank = degree[i] + degree[j];
21 if (direct.count(i * n + j)) rank--;
22 max_rank = max(max_rank, rank);
23 }
24 }
25 return max_rank;
26}We maintain an array to count the degrees for each city. To check direct connections, we structure them into an integer using a set. This is used to calculate the network rank by summing degrees, adjusted by direct connections.
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.