图题目：最大网络秩

题目

标题和出处

标题：最大网络秩

出处：1615. 最大网络秩

难度

4 级

题目描述

要求

由 $\text{n}$ 座城市和一些连接这些城市的道路 $\text{roads}$ 共同组成一个基础设施网络。每个 ${\text{roads[i] = [a}}_{\text{i}}{\text{, b}}_{\text{i}}\text{]}$ 表示在城市 ${\text{a}}_{\text{i}}$ 和 ${\text{b}}_{\text{i}}$ 之间有一条双向道路。

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

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

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

示例

示例 1：

输入：$\text{n = 4, roads = [[0,1],[0,3],[1,2],[1,3]]}$
输出：$\text{4}$
解释：城市 $\text{0}$ 和 $\text{1}$ 的网络秩是 $\text{4}$，因为共有 $\text{4}$ 条道路与城市 $\text{0}$ 或 $\text{1}$ 相连。位于 $\text{0}$ 和 $\text{1}$ 之间的道路只计算一次。

示例 2：

输入：$\text{n = 5, roads = [[0,1],[0,3],[1,2],[1,3],[2,3],[2,4]]}$
输出：$\text{5}$
解释：共有 $\text{5}$ 条道路与城市 $\text{1}$ 或 $\text{2}$ 相连。

示例 3：

输入：$\text{n = 8, roads = [[0,1],[1,2],[2,3],[2,4],[5,6],[5,7]]}$
输出：$\text{5}$
解释：$\text{2}$ 和 $\text{5}$ 的网络秩是 $\text{5}$，注意并非所有的城市都需要相连。

数据范围

• $\text{2}\le \text{n}\le \text{100}$
• $\text{0}\le \text{roads.length}\le \frac{\text{n}\times \text{(n}-\text{1)}}{\text{2}}$
• $\text{roads[i].length}=\text{2}$
• $\text{0}\le {\text{a}}_{\text{i}}{\text{, b}}_{\text{i}}\le \text{n}-\text{1}$
• ${\text{a}}_{\text{i}}\le {\text{b}}_{\text{i}}$
• 每对城市之间最多只有一条道路相连

解法

思路和算法

将整个基础设施网络看成无向图，每一座城市是一个结点，每条道路是一条无向边。根据网络秩的定义，两座不同的城市 $a$ 和 $b$ 构成的城市对的网络秩为与城市 $a$ 或城市 $b$ 直接相连的道路总数，即图中与结点 $a$ 或结点 $b$ 关联的边数。

在无向图中，一个结点的度为与该结点关联的边数，因此为了计算城市 $a$ 和城市 $b$ 构成的城市对的网络秩，需要知道结点 $a$ 和结点 $b$ 的度。当结点 $a$ 和结点 $b$ 不邻接时，计算结点 $a$ 和结点 $b$ 的度之和，即为网络秩；当结点 $a$ 和结点 $b$ 邻接时，存在一条边连接结点 $a$ 和结点 $b$，计算结点 $a$ 和结点 $b$ 的度之和会将连接结点 $a$ 和结点 $b$ 的边重复计算，因此结点 $a$ 和结点 $b$ 的度之和减 $1$ 为网络秩。

根据上述分析可知，计算两座城市构成的城市对的网络秩时，需要知道这两座城市对应的结点的度，以及这两个结点是否邻接。遍历全部道路，即可得到图中每个结点的度以及每一对结点是否邻接。使用数组记录每个结点的度，使用邻接矩阵记录每一对结点是否相邻。

在得到每个结点的度以及每一对结点是否邻接的信息之后，遍历每一对结点计算网络秩，遍历结束之后即可得到最大网络秩。

代码

class Solution {
    public int maximalNetworkRank(int n, int[][] roads) {
        int[] degrees = new int[n];
        boolean[][] connected = new boolean[n][n];
        for (int[] road : roads) {
            int city0 = road[0], city1 = road[1];
            degrees[city0]++;
            degrees[city1]++;
            connected[city0][city1] = true;
            connected[city1][city0] = true;
        }
        int maxRank = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int rank = degrees[i] + degrees[j] - (connected[i][j] ? 1 : 0);
                maxRank = Math.max(maxRank, rank);
            }
        }
        return maxRank;
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$，其中 $n$ 是城市数。需要遍历图中的每条边得到图中每个结点的度以及每一对结点是否邻接，然后遍历每一对结点计算网络秩，由于图中的边数最多为 $O(n^2)$，图中的结点对的数量为 $O(n^2)$，因此时间复杂度是 $O(n^2)$。

• 空间复杂度：$O(n^2)$，其中 $n$ 是城市数。需要 $O(n)$ 的空间记录每个城市对应的结点的度，以及 $O(n^2)$ 的空间记录邻接矩阵，因此空间复杂度是 $O(n^2)$。