题目描述
思路解析
一句话答案：LeetCode 1615 最大网络秩：一个点连着几条边就是它的度数，两城的秩等于各自度数相加，若之间直接有路就把重复那条减 1，枚举所有城市对取最大，时间 O(n²)。
从所有城市对里挑网络秩最大的一对
给一个整数 n 表示城市数、一个数组 roads，roads[i]=[a,b] 表示城市 a、b 之间有一条双向道路。两座不同城市的网络秩，是和这两座城任意一座直接相连的道路总数；若它俩之间也有一条路，这条只算一次。要的是所有城市对里最大的网络秩。题面例子 n=4、roads=[[0,1],[0,3],[1,2],[1,3]]，答案是 4。
盯着度数最高的两座城，不一定是答案
既然网络秩要度数大，那就找度数最高的两座城配对，这个直觉会栽跟头。度数最高的两座城之间要是有公共路，合并得减一次，秩反而缩水；换一个度数次高、和它没公共路的城搭配，不用减，可能后来居上。另外两座城不要求彼此连通，从互不相连的两块各取一座也能凑成一对。
网络秩为什么等于度数相加再看要不要减 1
先说度数，一个点连着几条边就是它的度数。城市 a 和 b 的度数相加得 deg[a]+deg[b]。但要是 a、b 之间本身有路，这条在 deg[a]、deg[b] 里各算了一次，重复了，得减 1；两城不相邻就不减。于是这一对的网络秩就是 deg[a]+deg[b]-(a 与 b 是否相邻)，剩下的是把所有不同城市对枚举一遍取最大。
两层循环怎么枚举、相邻怎么判
先扫一遍 roads 数度数：每读到一条 [a,b]，deg[a]、deg[b] 各加 1，同时把 a、b 互相记进对方的邻居集合，这张记录每个点连到谁的表就是邻接表。接着两层循环，外层 a 从 0 到 n-1，内层 b 从 a+1 起——从 a+1 开始既跳过自己配自己，又保证同一对不被正反重复算。每对算 deg[a]+deg[b]，查 a 在不在 b 的邻居里，在就减 1，和当前最大比一比大就更新。
拿 4 座城市的例子把 6 对全算一遍
先数度数。读 [0,1]，deg[0]、deg[1] 各成 1；读 [0,3]，deg[0] 成 2、deg[3] 成 1；读 [1,2]，deg[1] 成 2、deg[2] 成 1；读 [1,3]，deg[1] 成 3、deg[3] 成 2。最后 deg=[2,3,1,2]。
再枚举 6 对。(0,1)：2+3=5，两城相邻减 1，秩 4。(0,2)：2+1=3，不相邻，秩 3。(0,3)：2+2=4，相邻减 1，秩 3。(1,2)：3+1=4，相邻减 1，秩 3。(1,3)：3+2=5，相邻减 1，秩 4。(2,3)：1+2=3，不相邻，秩 3。秩 4 最高，出在城市对 (0,1)，与题面答案吻合。
枚举量是 n 平方，几种边界得心里有数
数度数扫一遍 roads 是 O(E)，E 是道路条数；枚举城市对是 n 乘 (n-1) 除以 2 对，每对常数次运算，是 O(n²)，这也是主项，n 不大不会超时。空间看实现：邻接矩阵配度数数组是 O(n²)，邻居集合的字典是 O(n+E)。
几个边界别踩空：一座城没有任何路，它参与的对全靠另一座城撑度数，也要入枚举；相邻两座城无论度数多高都要减 1，不减就把公共路重复算进去；答案里两座城不必彼此连通，跨过不同片区选一对，反而可能拿到更大的秩。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢这条主线:先数度数,再枚举每一对城市。每对的网络秩就是两边度数相加,如果这两座城之间有直接道路,再减掉重复的那一次。下面先把 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题