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 != bi- Each pair of cities has at most one road connecting them.
Python3
class Solution:
def maximalNetworkRank(self, n, roads):
graph = [[] for _ in range(n)]
for a, b in roads:
graph[a].append(b)
graph[b].append(a)
max_rank = 0
for i in range(n):
for j in range(i + 1, n):
rank = len(graph[i]) + len(graph[j])
if j in graph[i] or i in graph[j]:
rank -= 1
max_rank = max(max_rank, rank)
return max_rank
Explanation
The code defines a class `Solution` with a single method `maximalNetworkRank` that calculates the maximal network rank of a network represented by a list of roads connecting nodes in a graph.
Let's break down the code step by step:
1. Class and Method Definition:
class Solution:
def maximalNetworkRank(self, n, roads):
Here, a class named `Solution` is defined with a single method `maximalNetworkRank`. This method takes two arguments:
`n`, the number of nodes in the graph, and `roads`, a list of tuples representing roads between nodes.
2. Graph Initialization:
graph = [[] for _ in range(n)]
An empty adjacency list graph is initialized. The list has `n` empty lists, each representing the neighbors of a node.
3. Creating the Graph:
for a, b in roads:
graph[a].append(b)
graph[b].append(a)
The code iterates through each tuple `(a, b)` in the `roads` list. It then adds node `b` to the adjacency list of node `a` and vice versa, effectively creating an undirected graph.
4. Calculating Maximal Network Rank:
max_rank = 0
for i in range(n):
for j in range(i + 1, n):
rank = len(graph[i]) + len(graph[j])
if j in graph[i] or i in graph[j]:
rank -= 1
max_rank = max(max_rank, rank)
Two nested loops iterate over all pairs of nodes `(i, j)` such that `i` is less than `j`. For each pair, the code calculates the network rank, which is the sum of the number of neighbors of nodes `i` and `j`. If there's a direct connection between nodes `i` and `j` (i.e., they are neighbors), the rank is decremented by 1 to avoid double counting.
The maximal network rank is then updated to be the maximum between the current maximal rank and the rank calculated for the current pair `(i, j)`.
5. Returning Maximal Network Rank:
return max_rank
After calculating the maximal network rank for all possible pairs of nodes, the method returns the final maximum rank.
In summary, the `maximalNetworkRank` method constructs an undirected graph from the given roads, iterates over all pairs of nodes, calculates the network rank for each pair, and returns the maximal network rank achieved in the graph. This algorithm is aimed at finding the maximum potential connectivity between nodes in the graph.
Do you dream of turning your thoughts and words into income ? join us now and become blogger now.
0 Comments
Leave a Comment