LeetCode 1615. 最大网络秩
目录
题目描述
题意分析
有
n座城市和若干条双向道路。任意两座不同城市的「网络秩」定义为：与这两座城市中至少一座直接相连的道路总条数。要求返回所有城市对里网络秩的最大值。定义里的关键词是「至少一座」，也就是说这是两个道路集合的并集大小，而不是简单相加。如果两城之间恰好有一条直连道路，这条路同时属于两个集合，相加时会被算两次，必须扣掉一次。
用度数语言写出来就是：
rank(a, b) = degree[a] + degree[b] - (a 与 b 直连 ? 1 : 0)。整道题的全部数学内容就是这一行。城市数上限只有 100，道路数不超过
n * (n - 1) / 2，也就是最多约 5000 条。这个规模非常宽松：枚举所有城市对只有 4950 组，配上 $O(1)$ 的直连判定，总代价微不足道。规模在明确告诉你「不要去想什么巧妙的贪心，直接枚举点对就是标准解」。题目保证道路不重复且没有自环，所以「两城之间是否直连」是一个非零即一的布尔量，不会出现重边导致要扣 2 的情况。
边界上，若一条道路都没有，任意点对的秩都是 0；若某座城市孤立，它与任何城市配对的秩就等于对方的度数。
解法：度数 + 直连判定
核心思路
两座城市的网络秩，是所有至少连接其中一座城市的道路数。先统计每座城市的度数
degree，那么城市a、b的度数和已经包含全部相关道路。唯一需要修正的是两城之间的直连道路：它在
degree[a]和degree[b]中各被统计一次，但并集里只能算一次。因此：
rank(a, b) = degree[a] + degree[b] - (a 与 b 直连 ? 1 : 0)。题目规模允许枚举所有无序城市对。用邻接矩阵记录是否直连，可以在 $O(1)$ 时间完成修正。
不变量：处理完道路后，
degree[x]等于城市x的道路数，connected[a][b]准确表示两城是否存在直连道路；枚举过程中answer是已检查城市对的最大网络秩。正确性：两座城市的关联道路集合大小等于两个度数之和减去交集。无重边且无自环时，交集只有两城直连的那一条道路，大小为 0 或 1。公式因此精确计算每一对的秩，而枚举覆盖所有不同城市对，最大值即为答案。
解题步骤
- 扫描道路，同时增加两个端点的度数，并在邻接矩阵中双向标记直连。
- 枚举所有
a < b的无序城市对。- 计算度数和；若两城直连则减 1，并更新最大值。
对
n = 4、roads = [[0,1],[0,3],[1,2],[1,3]]，degree[0] = 2、degree[1] = 3，两城直连，所以秩为2 + 3 - 1 = 4。没有道路时所有度数为 0，答案自然为 0；两城不直连时不能减 1；道路是无向的，矩阵必须同时标记
[a][b]和[b][a]。
代码实现
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
int[] degree = new int[n];
boolean[][] connected = new boolean[n][n];
for (int[] road : roads) {
int a = road[0];
int b = road[1];
degree[a]++;
degree[b]++;
connected[a][b] = true;
connected[b][a] = true;
}
int answer = 0;
for (int a = 0; a < n; a++) {
for (int b = a + 1; b < n; b++) {
int rank = degree[a] + degree[b];
if (connected[a][b]) {
rank--;
}
answer = Math.max(answer, rank);
}
}
return answer;
}
}
func maximalNetworkRank(n int, roads [][]int) int {
degree := make([]int, n)
connected := make([][]bool, n)
for i := range connected {
connected[i] = make([]bool, n)
}
for _, road := range roads {
a, b := road[0], road[1]
degree[a]++
degree[b]++
connected[a][b] = true
connected[b][a] = true
}
answer := 0
for a := 0; a < n; a++ {
for b := a + 1; b < n; b++ {
rank := degree[a] + degree[b]
if connected[a][b] {
rank--
}
if rank > answer {
answer = rank
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n^2 + m)$，其中
m是道路数；预处理道路后枚举所有城市对。- 空间复杂度：$O(n^2)$，邻接矩阵占主导，度数数组为 $O(n)$。
关键点总结
- 网络秩是两组关联道路的并集大小，必须用容斥修正共同道路。
- 两城直连时只减 1，不直连时不减。
- 先预处理度数与直连关系，使每对城市的计算为常数时间。
- 枚举
a < b可避免重复并排除同一城市与自身配对。
易错点总结
- 直接相加两个度数：直连道路会被重复计算一次。
- 无论是否直连都减 1：不相邻城市的网络秩会被低估。
- 直连时减 2：并集只需去掉一份重复，不是去掉整条道路的两次计数。
- 邻接矩阵只标记一个方向：输入端点顺序可能与枚举顺序相反。
- 只检查度数最大的固定两点：直连修正可能让另一对城市得到更大网络秩。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 997. 找到小镇的法官 | 简单 | 靠入度与出度的组合条件唯一确定答案，同属「度数即答案」的建模 |
| 277. 搜寻名人 | 中等 | 同样以出入度刻画目标节点，但查询有次数限制需要先线性淘汰候选 |
| 547. 省份数量 | 中等 | 输入本身就是邻接矩阵，考的是在矩阵上做连通分量统计而非度数 |
| 310. 最小高度树 | 中等 | 需要按度数为 1 逐层剥离，度数是过程量而不是直接答案 |
| 697. 数组的度 | 简单 | 「度」的另一种语境，先统计频次再回头找最短覆盖区间 |
| 1584. 连接所有点的最小费用 | 中等 | 同为稠密图上的 $O(n^2)$ 枚举，但目标是最小生成树而非单对最优 |