Maximal Network Rank
给n个点和一个数组的edges的无向图, 问任意两点中的边最多多少.
这个看似是图的题..实际是一个counting problem. 注意一下corner case.
|
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 |
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; } } |