最大网络秩 图解题解
这道题到底在问什么
- 输入
- n=4, roads=[[0,1],[0,3],[1,2],[1,3]]
- 输出
- 4
- 输入
- n=5, roads=[[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
- 输出
- 5
先想最直接的笨办法
记牢这条主线:先数度数,再枚举每一对城市。每对的网络秩就是两边度数相加,如果这两座城之间有直接道路,再减掉重复的那一次。下面先把 4 座城市的度数一条路一条路地数出来。（动画第 3 步）
最优解：一步一步想明白
- 3记牢这条主线:先数度数,再枚举每一对城市。每对的网络秩就是两边度数相加,如果这两座城之间有直接道路,再减掉重复的那一次。下面先把 4 座城市的度数一条路一条路地数出来。
- 4准备数度数:每条道路给它的两个端点各加 1舞台上是 4 座城市,编号 0 到 3,城市之间的连线就是道路。开始时所有度数都记为 0。接下来扫描每一条道路,它连着哪两座城,就给这两座城的度数各加 1。
- 5城市 0 度数到 1,城市 1 度数到 1第 1 条道路连着城市 0 和城市 1。给这两座城的度数各加 1:城市 0 的度数变成 1,城市 1 的度数变成 1。节点旁边的小数字就是当前度数。
- 6城市 0 度数到 2,城市 3 度数到 1第 2 条道路连着城市 0 和城市 3。给这两座城的度数各加 1:城市 0 的度数变成 2,城市 3 的度数变成 1。节点旁边的小数字就是当前度数。
- 7城市 1 度数到 2,城市 2 度数到 1第 3 条道路连着城市 1 和城市 2。给这两座城的度数各加 1:城市 1 的度数变成 2,城市 2 的度数变成 1。节点旁边的小数字就是当前度数。
- 8城市 1 度数到 3,城市 3 度数到 2第 4 条道路连着城市 1 和城市 3。给这两座城的度数各加 1:城市 1 的度数变成 3,城市 3 的度数变成 2。节点旁边的小数字就是当前度数。
- 9城市 0:2,城市 1:3,城市 2:1,城市 3:24 条路都数完了。城市 0 的度数是 2,城市 1 是 3,城市 2 是 1,城市 3 是 2。度数这一步是基础,后面每一对城市的网络秩都从这四个数字里取。注意城市 1 度数最高,但它最终不一定独占最优,要看搭配哪座城、它们之间是否有公共路。
- 104 座城市两两组合,一共 6 对,逐对算网络秩度数有了,现在两层循环枚举所有不同城市对。4 座城市两两组合一共 6 对:(0,1) (0,2) (0,3) (1,2) (1,3) (2,3)。每一对都按同一个公式算:两边度数相加,再看它们之间有没有直接道路决定要不要减 1。逐对比较,留最大的。
- 11先相加:2 + 3 = 5,二者之间有路看城市对 (0, 1)。城市 0 度数 2,城市 1 度数 3,先相加得 5。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
- 12网络秩 = 5 - 1 = 4,刷新最优为 4城市对 (0, 1) 的网络秩 = 5 减去重复的 1 = 4。它比之前的最优大,把最优更新成 4,最优城市对记成 (0, 1)。
- 13先相加:2 + 1 = 3,二者之间无直接路看城市对 (0, 2)。城市 0 度数 2,城市 2 度数 1,先相加得 3。再看这两座城之间没有直接道路,不存在重复计数,不用减。
- 14网络秩 = 3 - 0 = 3,当前最优仍是 4城市对 (0, 2) 的网络秩 = 3 减 0 = 3。它没超过当前最优 4,最优不变。
- 15先相加:2 + 2 = 4,二者之间有路看城市对 (0, 3)。城市 0 度数 2,城市 3 度数 2,先相加得 4。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
- 16网络秩 = 4 - 1 = 3,当前最优仍是 4城市对 (0, 3) 的网络秩 = 4 减去重复的 1 = 3。它没超过当前最优 4,最优不变。
- 17先相加:3 + 1 = 4,二者之间有路看城市对 (1, 2)。城市 1 度数 3,城市 2 度数 1,先相加得 4。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
- 18网络秩 = 4 - 1 = 3,当前最优仍是 4城市对 (1, 2) 的网络秩 = 4 减去重复的 1 = 3。它没超过当前最优 4,最优不变。
- 19先相加:3 + 2 = 5,二者之间有路看城市对 (1, 3)。城市 1 度数 3,城市 3 度数 2,先相加得 5。再看这两座城之间正好有一条直接道路,那条路被双方各数了一次,待会儿要减掉重复的一次。
- 20网络秩 = 5 - 1 = 4,当前最优仍是 4城市对 (1, 3) 的网络秩 = 5 减去重复的 1 = 4。它没超过当前最优 4,最优不变。
- 21先相加:1 + 2 = 3,二者之间无直接路看城市对 (2, 3)。城市 2 度数 1,城市 3 度数 2,先相加得 3。再看这两座城之间没有直接道路,不存在重复计数,不用减。
- 22网络秩 = 3 - 0 = 3,当前最优仍是 4城市对 (2, 3) 的网络秩 = 3 减 0 = 3。它没超过当前最优 4,最优不变。
- 23最优城市对 (0, 1),网络秩 46 对城市全比完了。最大网络秩出现在城市对 (0, 1),值是 4。回看一眼:城市 0 度数 2、城市 1 度数 3,它们之间有一条公共路,网络秩 = 2 + 3 - 1 = 4。整道题就是先数度数,再枚举所有对、把相邻的那一次重复减掉,取最大。
⚠️ 容易写错的地方
✗ 错：两边度数直接相加就当网络秩
✓ 对：相邻城市对要减去重复的 1
a 到 b 那条公共路在 deg[a] 和 deg[b] 里各被数了一次,合并成「与这对相连的路总数」时只能算一次,不减就重复计数
✗ 错：默认选度数最大的两座城就对
✓ 对：要枚举所有对比较
两个度数最高的城如果之间有路要减 1,可能不如一个次高、一个无公共路的搭配,必须逐对算
✗ 错：把一座城市和自己配成一对
✓ 对：只统计两座不同城市
题目要的是不同城市对,自己和自己不构成城市对,枚举时内层从 a+1 起就能跳过
✗ 错：以为所有城市必须连通才有解
✓ 对：网络可以不连通,跨片也能选对
城市对不要求两座城之间有路相连,完全可以从两个互不相连的部分各取一座,后面边界演示里跨片选 (0,2) 就能拿到更大的网络秩
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
int maximalNetworkRank(int n, vector<vector<int>>& roads) {
int cnt[n];
int g[n][n];
memset(cnt, 0, sizeof(cnt));
memset(g, 0, sizeof(g));
for (auto& r : roads) {
int a = r[0], b = r[1];
g[a][b] = g[b][a] = 1;
++cnt[a];
++cnt[b];
}
int ans = 0;
for (int a = 0; a < n; ++a) {
for (int b = a + 1; b < n; ++b) {
ans = max(ans, cnt[a] + cnt[b] - g[a][b]);
}
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
int[][] g = new int[n][n];
int[] cnt = new int[n];
for (int[] r : roads) {
int a = r[0], b = r[1];
g[a][b] = 1;
g[b][a] = 1;
++cnt[a];
++cnt[b];
}
int ans = 0;
for (int a = 0; a < n; ++a) {
for (int b = a + 1; b < n; ++b) {
ans = Math.max(ans, cnt[a] + cnt[b] - g[a][b]);
}
}
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)。都不随枚举次数额外增长
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大网络秩 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么直接两层循环枚举所有城市对就够,不用更巧的算法?+
因为题目里城市数 n 不大,两两组合是 n 乘 (n-1) 除以 2 对,平方级别的枚举量完全在可接受范围。每对只做常数次运算:取两个度数相加、查一下是否相邻、和当前最大值比较。先 O(E) 数完度数和相邻关系,再 O(n²) 枚举,总复杂度 O(n² + E),简单直接又不会超时。题目规模没逼着你去想更复杂的优化。
相邻信息用邻接矩阵还是邻居集合,怎么选?+
都行,看 n 的规模。n 不大时,开一个 n 乘 n 的 0 或 1 邻接矩阵最直接,查 g[a][b] 是常数时间,参考代码的 C plus plus 和 Java 就是这么写的。如果 n 很大、道路相对稀疏,邻接矩阵会浪费 O(n²) 的空间,这时改用邻居集合的字典更省,判相邻看 a 在不在 g[b] 里也是接近常数,Python 版就用集合。这题 n 小,两种都不会有压力。
如果题目改成求最小网络秩,思路要变吗?+
主体不变,还是先数度数、再枚举所有不同城市对、对每对算同样的网络秩公式。区别只在最后的比较:求最大时留较大的,求最小时把初始答案设成一个很大的数,每对取较小的。公式本身、减去相邻那一次的逻辑都一模一样,改的只是「比大还是比小」这一处。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大网络秩 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。