05 August 2008
n 座城市和一些连接这些城市的道路 roads 共同组成一个基础设施网络。每个 roads[i] = [ai, bi] 都表示在城市 ai 和 bi 之间有一条双向道路。
两座不同城市构成的 城市对 的 网络秩 定义为：与这两座城市 直接 相连的道路总数。如果存在一条道路直接连接这两座城市，则这条道路只计算 一次 。
整个基础设施网络的 最大网络秩 是所有不同城市对中的 最大网络秩 。
给你整数 n 和数组 roads，返回整个基础设施网络的 最大网络秩 。
保存所有道路（已排序），对任意两点穷举他们的路径后找出最大
邻接矩阵，总时间复杂度O(N^2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
int[][] map =new int[n][n];//邻接矩阵
int[] degree =new int[n];//出度
for (int[] road : roads) {
map[road[0]][road[1]]++;
map[road[1]][road[0]]++;
degree[road[0]]++;
degree[road[1]]++;
}
int ans =Integer.MIN_VALUE;
for (int i = 0; i <n-1 ; i++) {
for (int j = i+1; j <n ; j++) {
int temp = degree[i]+degree[j]-map[i][j]; //出度和减去重复的边
ans = Math.max(ans,temp);
}
}
return ans;
}
}
邻接表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
List<Set<Integer>> list = new ArrayList<>();
int k = roads.length;
if(k == 0){
return 0;
}
for(int i = 0 ; i < n; i++){
list.add(new HashSet<>());
}
for(int i = 0; i < k; i++){
int a = roads[i][0];
int b = roads[i][1];
list.get(a).add(b);
list.get(b).add(a);
}
int max = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i!=j){
int a = list.get(i).contains(j)?1:0;
int pre = list.get(i).size()+list.get(j).size()-a;
max = max>pre?max:pre;
}
}
}
return max;
}
}