Medium

题目描述

有 n 个城市和一些连接这些城市的道路。每个 roads[i] = [ai, bi] 表示在城市 ai 和 bi 之间有一条双向道路。

两个不同城市的网络秩定义为连接到任一城市的道路总数。如果一条道路直接连接两个城市，则只计算一次。

基础设施的最大网络秩是所有不同城市对的网络秩的最大值。

给定整数 n 和数组 roads，返回整个基础设施的最大网络秩。

示例 1:

输入：n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]
输出：4
解释：城市 0 和 1 的网络秩是 4，因为有 4 条道路连接到 0 或 1。0 和 1 之间的道路只计算一次。

示例 2:

输入：n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]
输出：5
解释：有 5 条道路连接到城市 1 或 2。

示例 3:

输入：n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]
输出：5
解释：城市 2 和 5 的网络秩是 5。注意不是所有城市都必须连接。

约束条件:

  • 2 <= n <= 100
  • 0 <= roads.length <= n * (n - 1) / 2
  • roads[i].length == 2
  • 0 <= ai, bi <= n-1
  • ai != bi
  • 每对城市最多有一条道路连接它们。

解题思路

这道题要求找出所有城市对中网络秩的最大值。网络秩的定义是两个城市连接道路数的总和，如果两个城市之间有直接连接，则需要减去1（避免重复计算）。

解题思路：

  1. 统计度数：首先遍历所有道路，计算每个城市的度数（连接的道路数）
  2. 建立连接关系：使用邻接矩阵或集合记录城市间是否直接相连
  3. 枚举所有城市对：对于每一对不同的城市(i,j)，计算它们的网络秩
  4. 计算网络秩：网络秩 = degree[i] + degree[j] - (如果i和j直接相连则减1，否则减0)
  5. 维护最大值：记录所有城市对中网络秩的最大值

优化思路：

  • 可以先找出度数最大的几个城市，优先考虑它们的组合
  • 使用集合存储边的关系，便于快速查询两城市是否相连

时间复杂度是O(n²)，空间复杂度是O(n²)，对于n≤100的约束完全可以接受。

代码实现

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<int> degree(n, 0);
        set<pair<int, int>> connected;
        
        for (auto& road : roads) {
            int u = road[0], v = road[1];
            degree[u]++;
            degree[v]++;
            connected.insert({min(u, v), max(u, v)});
        }
        
        int maxRank = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int rank = degree[i] + degree[j];
                if (connected.count({i, j})) {
                    rank--;
                }
                maxRank = max(maxRank, rank);
            }
        }
        
        return maxRank;
    }
};

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        degree = [0] * n
        connected = set()
        
        for u, v in roads:
            degree[u] += 1
            degree[v] += 1
            connected.add((min(u, v), max(u, v)))
        
        max_rank = 0
        for i in range(n):
            for j in range(i + 1, n):
                rank = degree[i] + degree[j]
                if (i, j) in connected:
                    rank -= 1
                max_rank = max(max_rank, rank)
        
        return max_rank

public class Solution {
    public int MaximalNetworkRank(int n, int[][] roads) {
        int[] degree = new int[n];
        HashSet<(int, int)> connected = new HashSet<(int, int)>();
        
        foreach (var road in roads) {
            int u = road[0], v = road[1];
            degree[u]++;
            degree[v]++;
            connected.Add((Math.Min(u, v), Math.Max(u, v)));
        }
        
        int maxRank = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int rank = degree[i] + degree[j];
                if (connected.Contains((i, j))) {
                    rank--;
                }
                maxRank = Math.Max(maxRank, rank);
            }
        }
        
        return maxRank;
    }
}

var maximalNetworkRank = function(n, roads) {
    const degree = new Array(n).fill(0);
    const connected = new Set();
    
    for (const [u, v] of roads) {
        degree[u]++;
        degree[v]++;
        connected.add(`${Math.min(u, v)}-${Math.max(u, v)}`);
    }
    
    let maxRank = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            let rank = degree[i] + degree[j];
            if (connected.has(`${i}-${j}`)) {
                rank--;
            }
            maxRank = Math.max(maxRank, rank);
        }
    }
    
    return maxRank;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大O表示法
时间复杂度O(n² + m)
空间复杂度O(n + m)

其中 n 是城市数量，m 是道路数量。时间复杂度主要来自于枚举所有城市对的O(n²)操作，空间复杂度主要用于存储度数数组和连接关系。