题目描述

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

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

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

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

样例

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

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

输入：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
• 每对城市之间 最多只有一条 道路相连。

算法

(暴力枚举) $O(n^2 + m)$

1. 对于每个点预处理一个集合，记录其相邻的点。
2. 暴力枚举点对，对于该点对的秩可以由两个点的相邻点个数求和得到，但需要特判一下这两个点之间是否有直接相连。如果有直接相连，则秩减去 1。
3. 找到秩最大的点对。

时间复杂度

• 预处理的时间复杂度为 $O(n + m)$。
• 点对的组合为 $O(n^2)$ 种，每次判断仅需要常数的时间。
• 故总时间复杂度为 $O(n^2 + m)$。

空间复杂度

• 需要 $O(n + m)$ 的额外空间记录每个点的相邻点集合。

C++ 代码

class Solution {
public:
    int maximalNetworkRank(int n, vector<vector<int>>& roads) {
        vector<unordered_set<int>> graph(n);
        for (const auto &e : roads) {
            graph[e[0]].insert(e[1]);
            graph[e[1]].insert(e[0]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) {
                int cur = graph[i].size() + graph[j].size();
                if (graph[i].find(j) != graph[i].end())
                    cur--;
                if (ans < cur)
                    ans = cur;
            }

        return ans;
    }
};