LeetCode 1615. 最大网络秩

约 4 分钟
文章信息 6 个分类 1 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 微软
标签
图

题目描述

✅ 1615. 最大网络秩

image-20260929085330261

image-20260929085330440

题意分析

选择两座不同城市，统计与其中至少一座直接相连的道路总数，每条道路只算一次。两座城市本身不必相连，需要在所有城市对中寻找最大值。

解法：度数 + 直连判定

核心思路

[!blue]
用 degree[a] 记录城市 a 连接的道路数。对于一对城市 a、b，degree[a] + degree[b] 已经包含与它们相关的全部道路，只需处理重复计数。

一条道路要同时出现在两个度数中，它的两个端点必须正好是 a 和 b。题目保证每对城市最多有一条道路，因此两城直连时减 $1$，不直连时无需扣减。两城即使拥有共同邻居，连接这个邻居的也是两条不同道路，都应计入。

用布尔邻接矩阵 connected[a][b] 记录直连关系，就能在常数时间算出任意一对城市的网络秩。枚举所有 a < b，每个无序城市对恰好计算一次，取最大值便覆盖了全部可能答案。城市数最多为 $100$，直接枚举所有城市对即可。

解题步骤

  1. 扫描道路，增加两个端点的度数并双向标记连接。
  2. 将答案初始化为 $0$，枚举全部 a < b 的城市对。
  3. 相加度数，直接相连时减一，更新最大值。
  4. 返回答案。没有道路时，所有度数和候选值都为 $0$，无需特殊分支。

代码实现

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^2)$，邻接矩阵占主导。

关键点总结

[!green]

  • 网络秩统计道路并集，并非不同邻居的数量。
  • 直连只扣掉一份重复，整条道路仍要算一次。
  • a<b 同时避免重复枚举和自身配对。

易错点总结

[!yellow]

  • 不扣直连重复边：相邻城市的秩被高估。
  • 直连时减二：把这条路完全移出了并集。
  • 邻接矩阵只写一个方向：输入端点顺序可能与枚举顺序相反。
  • 不相连也减一：无交集时不能扣减。

相似题目

题目 难度 关联与区别
2285. 道路的最大总重要性 中等 同样利用每条道路对两端度数的贡献，原题为全图分配权重，本题选两点并扣除它们之间的重复道路。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/41873232
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！