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;
    }
}