package leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.com/problems/maximal-network-rank/
 */
public class Problem1615 {
    public int maximalNetworkRank(int n, int[][] roads) {
        Set<String>[] graph = new Set[n];
        for (int[] road : roads) {
            if (graph[road[0]] == null) {
                graph[road[0]] = new HashSet<>();
            }
            String edge = edge(road[0], road[1]);
            graph[road[0]].add(edge);
            if (graph[road[1]] == null) {
                graph[road[1]] = new HashSet<>();
            }
            graph[road[1]].add(edge);
        }
        int answer = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Set<String> set1 = graph[i] != null ? graph[i] : new HashSet<>();
                Set<String> set2 = graph[j] != null ? graph[j] : new HashSet<>();
                Set<String> set = new HashSet<>();
                set.addAll(set1);
                set.addAll(set2);
                answer = Math.max(answer, set.size());
            }
        }
        return answer;
    }

    private static String edge(int a, int b) {
        return a < b ? a + "," + b : b + "," + a;
    }

    public static void main(String[] args) {
        Problem1615 prob = new Problem1615();
        System.out.println(prob.maximalNetworkRank(
            4, new int[][]{{0,1},{0,3},{1,2},{1,3}})); // 4
        System.out.println(prob.maximalNetworkRank(
            5, new int[][]{{0,1},{0,3},{1,2},{1,3},{2,3},{2,4}})); // 5
        System.out.println(prob.maximalNetworkRank(
            8, new int[][]{{0,1},{1,2},{2,3},{2,4},{5,6},{5,7}})); // 5
        System.out.println(prob.maximalNetworkRank(
            2, new int[][]{})); // 0
        System.out.println(prob.maximalNetworkRank(
            2, new int[][]{{1, 0}})); // 1
        System.out.println(prob.maximalNetworkRank(
            4, new int[][]{{1, 0}, {2, 3}})); // 2
        System.out.println(prob.maximalNetworkRank(
            3, new int[][]{{0, 2}, {0, 1}})); // 2
    }
}

@@ -16,57 +16,8 @@
 e;%0A%0A
-import java.util.HashSet;%0Aimport java.util.Set;%0A%0A
 /**%0A
@@ -172,37 +172,81 @@
     
-Set%3CString%3E%5B%5D graph = new Set
+int%5B%5D counts = new int%5Bn%5D;%0A        boolean%5B%5D%5B%5D connected = new boolean%5Bn%5D
 %5Bn%5D;
@@ -297,37 +297,26 @@
     
-if (graph%5Broad%5B0%5D%5D == null) %7B
+counts%5Broad%5B0%5D%5D++;
 %0A   
@@ -328,290 +328,121 @@
     
-    graph
+counts
 %5Broad%5B
-0%5D%5D = new HashSet%3C%3E();%0A            %7D%0A            String edge = edge(
+1%5D%5D++;%0A            connected%5B
 road%5B0%5D
-, 
+%5D%5B
 road%5B1%5D
-);%0A            graph%5Broad%5B0%5D%5D.add(edge);%0A            if (graph%5Broad%5B1%5D%5D == null) %7B%0A                graph
+%5D = true;%0A            connected%5Broad%5B1%5D%5D
 %5Broad%5B
-1
+0
 %5D%5D = 
-new HashSet%3C%3E();%0A            %7D%0A            graph%5Broad%5B1%5D%5D.add(edge)
+true
 ;%0A  
@@ -577,1328 +577,132 @@
     
-Set%3CString%3E set1 = graph%5Bi%5D != null ? graph%5Bi%5D : new HashSet%3C%3E();%0A                Set%3CString%3E set2 = graph%5Bj%5D != null ? graph%5Bj%5D : new HashSet%3C%3E();%0A                Set%3CString%3E set = new HashSet%3C%3E();%0A                set.addAll(set1);%0A                set.addAll(set2);%0A                answer = Math.max(answer, set.size());%0A            %7D%0A        %7D%0A        return answer;%0A    %7D%0A%0A    private static String edge(int a, int b) %7B%0A        return a %3C b ? a + %22,%22 + b : b + %22,%22 + a;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1615 prob = new Problem1615();%0A        System.out.println(prob.maximalNetworkRank(%0A            4, new int%5B%5D%5B%5D%7B%7B0,1%7D,%7B0,3%7D,%7B1,2%7D,%7B1,3%7D%7D)); // 4%0A        System.out.println(prob.maximalNetworkRank(%0A            5, new int%5B%5D%5B%5D%7B%7B0,1%7D,%7B0,3%7D,%7B1,2%7D,%7B1,3%7D,%7B2,3%7D,%7B2,4%7D%7D)); // 5%0A        System.out.println(prob.maximalNetworkRank(%0A            8, new int%5B%5D%5B%5D%7B%7B0,1%7D,%7B1,2%7D,%7B2,3%7D,%7B2,4%7D,%7B5,6%7D,%7B5,7%7D%7D)); // 5%0A        System.out.println(prob.maximalNetworkRank(%0A            2, new int%5B%5D%5B%5D%7B%7D)); // 0%0A        System.out.println(prob.maximalNetworkRank(%0A            2, new int%5B%5D%5B%5D%7B%7B1, 0%7D%7D)); // 1%0A        System.out.println(prob.maximalNetworkRank(%0A            4, new int%5B%5D%5B%5D%7B%7B1, 0%7D, %7B2, 3%7D%7D)); // 2%0A        System.out.println(prob.maximalNetworkRank(%0A            3, new int%5B%5D%5B%5D%7B%7B0, 2%7D, %7B0, 1%7D%7D)); // 2
+answer = Math.max(answer, counts%5Bi%5D + counts%5Bj%5D - (connected%5Bi%5D%5Bj%5D ? 1 : 0));%0A            %7D%0A        %7D%0A        return answer;
 %0A   

Solve problem 1615