题目描述
思路解析动画文字版
记牢这条主线:先数度数,再枚举每一对城市。每对的网络秩就是两边度数相加,如果这两座城之间有直接道路,再减掉重复的那一次。下面先把 4 座城市的度数一条路一条路地数出来。
初始 · 4 座城市,度数全为 0：舞台上是 4 座城市,编号 0 到 3,城市之间的连线就是道路。开始时所有度数都记为 0。接下来扫描每一条道路,它连着哪两座城,就给这两座城的度数各加 1。
道路 1 / 4 · 连接城市 0 和 1：第 1 条道路连着城市 0 和城市 1。给这两座城的度数各加 1:城市 0 的度数变成 1,城市 1 的度数变成 1。节点旁边的小数字就是当前度数。
道路 2 / 4 · 连接城市 0 和 3：第 2 条道路连着城市 0 和城市 3。给这两座城的度数各加 1:城市 0 的度数变成 2,城市 3 的度数变成 1。节点旁边的小数字就是当前度数。
道路 3 / 4 · 连接城市 1 和 2：第 3 条道路连着城市 1 和城市 2。给这两座城的度数各加 1:城市 1 的度数变成 2,城市 2 的度数变成 1。节点旁边的小数字就是当前度数。
道路 4 / 4 · 连接城市 1 和 3：第 4 条道路连着城市 1 和城市 3。给这两座城的度数各加 1:城市 1 的度数变成 3,城市 3 的度数变成 2。节点旁边的小数字就是当前度数。
度数数完 · deg = [2, 3, 1, 2]：4 条路都数完了。城市 0 的度数是 2,城市 1 是 3,城市 2 是 1,城市 3 是 2。度数这一步是基础,后面每一对城市的网络秩都从这四个数字里取。注意城市 1 度数最高,但它最终不一定独占最优,要看搭配哪座城、它们之间是否有公共路。
开始枚举城市对 · 共 6 对：度数有了,现在两层循环枚举所有不同城市对。4 座城市两两组合一共 6 对:(0,1) (0,2) (0,3) (1,2) (1,3) (2,3)。每一对都按同一个公式算:两边度数相加,再看它们之间有没有直接道路决定要不要减 1。逐对比较,留最大的。
看城市对 (0, 1) · 度数 2 + 3 = 5：看城市对 (0, 1)。城市 0 度数 2,城市 1 度数 3,先相加得 5。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
城市对 (0, 1) 网络秩 = 4 · 刷新最优：城市对 (0, 1) 的网络秩 = 5 减去重复的 1 = 4。它比之前的最优大,把最优更新成 4,最优城市对记成 (0, 1)。
看城市对 (0, 2) · 度数 2 + 1 = 3：看城市对 (0, 2)。城市 0 度数 2,城市 2 度数 1,先相加得 3。再看这两座城之间没有直接道路,不存在重复计数,不用减。
城市对 (0, 2) 网络秩 = 3 · 不超过最优：城市对 (0, 2) 的网络秩 = 3 减 0 = 3。它没超过当前最优 4,最优不变。
看城市对 (0, 3) · 度数 2 + 2 = 4：看城市对 (0, 3)。城市 0 度数 2,城市 3 度数 2,先相加得 4。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
城市对 (0, 3) 网络秩 = 3 · 不超过最优：城市对 (0, 3) 的网络秩 = 4 减去重复的 1 = 3。它没超过当前最优 4,最优不变。
看城市对 (1, 2) · 度数 3 + 1 = 4：看城市对 (1, 2)。城市 1 度数 3,城市 2 度数 1,先相加得 4。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
城市对 (1, 2) 网络秩 = 3 · 不超过最优：城市对 (1, 2) 的网络秩 = 4 减去重复的 1 = 3。它没超过当前最优 4,最优不变。
看城市对 (1, 3) · 度数 3 + 2 = 5：看城市对 (1, 3)。城市 1 度数 3,城市 3 度数 2,先相加得 5。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
城市对 (1, 3) 网络秩 = 4 · 不超过最优：城市对 (1, 3) 的网络秩 = 5 减去重复的 1 = 4。它没超过当前最优 4,最优不变。
看城市对 (2, 3) · 度数 1 + 2 = 3：看城市对 (2, 3)。城市 2 度数 1,城市 3 度数 2,先相加得 3。再看这两座城之间没有直接道路,不存在重复计数,不用减。
城市对 (2, 3) 网络秩 = 3 · 不超过最优：城市对 (2, 3) 的网络秩 = 3 减 0 = 3。它没超过当前最优 4,最优不变。
枚举结束 · 最大网络秩 = 4：6 对城市全比完了。最大网络秩出现在城市对 (0, 1),值是 4。回看一眼:城市 0 度数 2、城市 1 度数 3,它们之间有一条公共路,网络秩 = 2 + 3 - 1 = 4。整道题就是先数度数,再枚举所有对、把相邻的那一次重复减掉,取最大。
边界想清:无路时网络秩为 0、相邻对要减到只剩 1、跨片选无公共路的两座城反而能拿到更大的网络秩。
面试重点:平方枚举足够、相邻信息按规模选矩阵或集合、改求最小只需把比较换成取较小值。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int: g = defaultdict(set) for a, b in roads: g[a].add(b) g[b].add(a) ans = 0 for a in range(n): for b in range(a + 1, n): if (t := len(g[a]) + len(g[b]) - (a in g[b])) > ans: ans = t return ans复杂度
- 时间：O(n² + E)，E 是道路条数。先扫一遍 roads 数度数、记相邻,是 O(E);再两层循环枚举所有不同城市对,一共 n 乘 (n-1) 除以 2 对,每对常数次运算,是 O(n²)。两段相加,主项是 O(n²)。题目里 n 不大,平方枚举完全够用
- 空间：取决于实现，按峰值算。Java 和 C plus plus 用 n 乘 n 的邻接矩阵加长度 n 的度数数组,峰值是 O(n²);Python 用邻居集合的字典,所有集合元素加起来是 O(n + E)。都不随枚举次数额外增长
易错点
面试追问把动画讲成自己的话
追问为什么直接两层循环枚举所有城市对就够,不用更巧的算法?
追问相邻信息用邻接矩阵还是邻居集合,怎么选?
追问如果题目改成求最小网络秩,思路要变吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
最小体力消耗路径
LeetCode 1631 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题