最大网络秩

标签: 图

难度: Medium

n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [a_i, b_i] 都表示在城市 a_i 和 b_i 之间有一条双向道路。

两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市直接相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算一次。

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

给你整数 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 <= a_i, b_i <= n-1
a_i != b_i
每对城市之间 最多只有一条 道路相连

Submission

运行时间: 43 ms

内存: 17.5 MB

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        # 实际只要枚举最大和次大即可,分为两类
        point = [[False] * n for _ in range(n)]
        cnt = [0] * n
        for x, y in roads:
            cnt[x] += 1
            cnt[y] += 1
            point[x][y] = True
            point[y][x] = True
        first = second = 0
        farr = sarr = []
        for i in range(n):
            if cnt[i] > first:
                farr, sarr = [i], farr
                first, second = cnt[i], first
            elif cnt[i] == first:
                farr.append(i)
            elif cnt[i] > second:
                sarr = [i]
                second = cnt[i]
            elif cnt[i] == second:
                sarr.append(i)
        t = len(farr)
        if t == 1:  # 只有一个最大
            i = farr.pop()
            return first + second - all(point[i][j] for j in sarr)  # 剩下从次大选
        else:  # 两个都从最大选
            for i in range(t):
                for j in range(i + 1, t):
                    if not point[farr[i]][farr[j]]:
                        return 2 * first
            return 2 * first - 1

Explain

此题解通过计算每座城市连接的道路数量并使用两个数组来追踪每个城市的道路数（cnt数组）以及是否有直接连接两座城市的道路（point矩阵）。首先，它记录了所有城市的道路数量，并识别出连接最多道路的城市（'first'）和次多的城市（'second'）。如果最多道路的城市有超过一个，则检查这些城市之间是否有直接连接的道路。如果没有直接连接，则它们的网络秩是两倍的'first'值。如果有直接连接的城市，则减去一，因为这条路被重复计算了一次。如果最大道路数的城市只有一个，那么需要检查与次大道路数城市之间的直接连接情况，并相应调整计算结果。

时间复杂度: O(n^2)

空间复杂度: O(n^2)

class Solution:
    def maximalNetworkRank(self, n: int, roads: List[List[int]]) -> int:
        # 初始化每个城市的连接矩阵和道路计数数组
        point = [[False] * n for _ in range(n)]
        cnt = [0] * n
        # 填充道路计数和直接连接的矩阵
        for x, y in roads:
            cnt[x] += 1
            cnt[y] += 1
            point[x][y] = True
            point[y][x] = True
        # 寻找连接最多和次多的城市
        first = second = 0
        farr = sarr = []
        for i in range(n):
            if cnt[i] > first:
                farr, sarr = [i], farr
                first, second = cnt[i], first
            elif cnt[i] == first:
                farr.append(i)
            elif cnt[i] > second:
                sarr = [i]
                second = cnt[i]
            elif cnt[i] == second:
                sarr.append(i)
        t = len(farr)
        if t == 1:  # 只有一个城市连接最多
            i = farr.pop()
            # 判断次大连接城市组是否有直接连接到该城市
            return first + second - all(point[i][j] for j in sarr)
        else:  # 从最大连接城市组中选择两个城市
            for i in range(t):
                for j in range(i + 1, t):
                    if not point[farr[i]][farr[j]]:
                        return 2 * first  # 无直接连接，直接返回双倍
            return 2 * first - 1  # 有直接连接，减去重复计数的道路

Explore

使用`cnt数组`和`point矩阵`这两种数据结构提高了算法的效率。`cnt数组`通过索引直接存储每个城市的道路数量，使得更新和查询道路数都是O(1)的时间复杂度。`point矩阵`作为二维布尔数组，直接记录任意两个城市之间是否存在直接连接，这使得查询两城市间的连接状态也是O(1)时间复杂度。整体上，这种数据结构的选择使得算法在处理连接查询和更新时非常高效，尤其是在频繁查询和少量更新的情况下，能够快速响应。

当有多个城市拥有相同的最高道路数时，这些城市之间的直接连接情况会直接影响网络秩的计算。如果这些城市之间没有直接连接，那么选择这两个城市作为网络的一部分将不会重复计算任何道路，因此网络秩是两者道路数的简单相加。然而，如果这些城市之间有直接连接的道路，选择这两个城市会导致这条道路被重复计算，因此需要从总和中减去这条重复的道路。这是为了确保网络秩的计算准确无误，避免重复计数。

在这种情况下，算法需要确定最大道路数的城市和次大道路数的城市之间是否存在直接连接。`all`函数在这里用于检查是否所有次大道路数城市与最大道路数城市之间都有直接连接。如果`all(point[i][j] for j in sarr)`返回`True`，这意味着每个次大道路数城市都与最大道路数的城市有直接连接，因此需要从总和`first + second`中减去1，避免重复计数道路。如果返回`False`，则表示至少有一个次大道路数城市与最大道路数城市没有直接连接，此时网络秩应为`first + second`。