[每日一题]1615.最大网络秩
1615. 最大网络秩 n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 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 相连。
提示：
- 2 <= n <= 100
- 0 <= roads.length <= n * (n - 1) / 2
- roads[i].length == 2
- 0 <= ai, bi <= n-1
- ai != bi
- 每对城市之间 最多只有一条 道路相连
Solutions
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
boolean[][] connected = new boolean[n][n];
int[] cnt = new int[n];
for (int[] road : roads) {
cnt[road[0]]++;
cnt[road[1]]++;
connected[road[0]][road[1]] = true;
connected[road[1]][road[0]] = true;
}
int max = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) {
continue;
}
int t = cnt[i] + cnt[j];
if (connected[i][j]) {
t--;
}
max = Math.max(max, t);
}
}
return max;
}
}
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
boolean[][] connect = new boolean[n][n];
int[] degree = new int[n];
for (int[] road : roads) {
int x = road[0], y = road[1];
connect[x][y] = true;
connect[y][x] = true;
degree[x]++;
degree[y]++;
}
int first = -1, second = -2;
List<Integer> firstArr = new ArrayList<Integer>();
List<Integer> secondArr = new ArrayList<Integer>();
for (int i = 0; i < n; ++i) {
if (degree[i] > first) {
second = first;
secondArr = new ArrayList<Integer>(firstArr);
first = degree[i];
firstArr.clear();
firstArr.add(i);
} else if (degree[i] == first) {
firstArr.add(i);
} else if (degree[i] > second){
secondArr.clear();
second = degree[i];
secondArr.add(i);
} else if (degree[i] == second) {
secondArr.add(i);
}
}
if (firstArr.size() == 1) {
int u = firstArr.get(0);
for (int v : secondArr) {
if (!connect[u][v]) {
return first + second;
}
}
return first + second - 1;
} else {
int m = roads.length;
if (firstArr.size() * (firstArr.size() - 1) / 2 > m) {
return first * 2;
}
for (int u : firstArr) {
for (int v : firstArr) {
if (u != v && !connect[u][v]) {
return first * 2;
}
}
}
return first * 2 - 1;
}
}
}//贪心
Ideas
-
枚举
根据题意可知，两座不同城市构成的城市对的网络秩定义为：与这两座城市直接相连的道路总数，这两座城市之间的道路只计算一次。假设城市 x 的度数为
degree[x]，则此时我们可以知道城市对(i,j)的网络秩为如下：如果 i 与 j 之间没有道路连接，则此时
(i,j)的网络秩为degree[i]+degree[j]； 如果 i 与 j 之间存在道路连接，则此时(i,j)的网络秩为degree[i]+degree[j]−1； 根据以上求网络秩的方法，我们首先求出所有城市在图中的度数，然后枚举所有可能的城市对(i,j)，求出城市对(i,j)的网络秩，即可找到最大的网络秩。