What is the definition of network rank in the Maximal Network Rank problem?

Network rank of two cities is the total number of roads connected to either city, counting a shared road only once.

Can cities with no connecting roads affect the maximal network rank?

Yes, cities with fewer connections reduce the network rank when paired, but the maximal rank is determined by the most connected pairs.

Is there a preferred data structure to track road connections efficiently?

An adjacency matrix or adjacency list works; the choice depends on balancing lookup speed and space usage for n cities.

How does GhostInterview help avoid common pitfalls in this problem?

It highlights shared road handling, ensures all city pairs are evaluated, and tracks counts systematically to prevent double-counting.

What strategy should I use for maximal network rank calculations?

Use a graph-driven approach: count connections per city, check all unique pairs, subtract shared roads, and track the maximum value.

#1615

Medium

auto_awesome图

LeetCode 题解工作台

最大网络秩

n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [a i , b i ] 都表示在城市 a i 和 b i 之间有一条双向道路。两座不同城市构成的城市对的网络秩定义为：与这两座城市直接相连的道路总数。如果存在一条道路直接连接这两座城…

图

题目描述

n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [a_i, b_i] 都表示在城市 a_i 和 b_i 之间有一条双向道路。

两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市直接相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算一次。

整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。

给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。

示例 1：

输入：n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
输出：4
解释：城市 0 和 1 的网络秩是 4，因为共有 4 条道路与城市 0 或 1 相连。位于 0 和 1 之间的道路只计算一次。

示例 2：

输入：n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
输出：5
解释：共有 5 条道路与城市 1 或 2 相连。

示例 3：

输入：n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
输出：5
解释：2 和 5 的网络秩为 5，注意并非所有的城市都需要连接起来。

提示：

2 <= n <= 100
0 <= roads.length <= n * (n - 1) / 2
roads[i].length == 2
0 <= a_i, b_i <= n-1
a_i != b_i
每对城市之间 最多只有一条 道路相连

lightbulb

解题思路

方法一：计数

我们可以用一维数组 $\textit{cnt}$ 记录每个城市的度，用二维数组 $\textit{g}$ 记录每对城市之间是否有道路相连，如果城市 $a$ 和城市 $b$ 之间有道路相连，则 $\textit{g}[a][b] = \textit{g}[b][a] = 1$ ，否则 $\textit{g}[a][b] = \textit{g}[b][a] = 0$ 。

接下来，我们枚举每对城市 $(a, b)$ ，其中 $a \lt b$ ，计算它们的网络秩，即 $\textit{cnt}[a] + \textit{cnt}[b] - \textit{g}[a][b]$ ，取其中的最大值即为答案。

时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 是城市的数量。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        g = [[0] * n for _ in range(n)]
        cnt = [0] * n
        for a, b in roads:
            g[a][b] = g[b][a] = 1
            cnt[a] += 1
            cnt[b] += 1
        return max(cnt[a] + cnt[b] - g[a][b] for a in range(n) for b in range(a + 1, n))

speed

复杂度分析

指标	值
时间	complexity is O(n^2) due to evaluating all city pairs. Space complexity is O(n^2) if using a matrix for direct road tracking, or O(n + m) using adjacency lists and counts, where m is the number of roads.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Focus on computing the network rank for each city pair correctly, especially handling shared roads.
question_mark
Optimize storage and access of road connections for fast lookup to avoid repeated scanning.
question_mark
Consider the trade-off between using an adjacency matrix versus adjacency list for space and speed.

warning

常见陷阱

外企场景

error
Double-counting a road that connects both cities when calculating network rank.
error
Forgetting to iterate through all unique pairs, potentially missing the maximal rank.
error
Using inefficient structures leading to excessive time complexity on larger n values.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Compute the second highest network rank instead of the maximal one.
arrow_right_alt
Allow multiple roads between the same pair of cities and adjust the counting logic.
arrow_right_alt
Extend to weighted roads where the network rank sums road weights rather than counts.

help

常见问题

外企场景

继续练习

#1632 矩阵转换后的排名 #1591 奇怪的打印机 II #1584 连接所有点的最小费用