Maximal Network Rank
给n个点和一个数组的edges的无向图, 问任意两点中的边最多多少.
这个看似是图的题..实际是一个counting problem. 注意一下corner case.
class Solution {
public int maximalNetworkRank(int n, int[][] roads) {
if(roads.length == 0)
return 0;
Map<Integer, Set<Integer>> map = new HashMap<>();
for(int[] r : roads) {
map.putIfAbsent(r[0], new HashSet<>());
map.putIfAbsent(r[1], new HashSet<>());
map.get(r[0]).add(r[1]);
map.get(r[1]).add(r[0]);
}
int max = 0;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int count = 0;
if(map.containsKey(i))
count += map.get(i).size();
if(map.containsKey(j))
count += map.get(j).size();
if(map.containsKey(j) && map.containsKey(i) && map.get(i).contains(j))
count--;
max = Math.max(max, count);
}
}
return max;
}
}