package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/loud-and-rich/
 */
public class Problem851 {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        Map<Integer, List<Integer>> graph = buildGraph(richer);
        int[] answers = new int[quiet.length];
        for (int i = 0; i < quiet.length; i++) {
            boolean[] visited = new boolean[quiet.length];
            Quietest quietest = new Quietest();
            dfs(graph, i, visited, quiet, quietest);
            answers[i] = quietest.index;
        }
        return answers;
    }

    private static class Quietest {
        private int value = Integer.MAX_VALUE;
        private int index = -1;
    }

    private static void dfs(Map<Integer, List<Integer>> graph,
                            int source,
                            boolean[] visited,
                            int[] quiet,
                            Quietest quietest) {
        if (quietest.value >= quiet[source]) {
            quietest.value = quiet[source];
            quietest.index = source;
        }
        visited[source] = true;
        List<Integer> adjacents = graph.get(source);
        if (adjacents == null) {
            return;
        }
        for (int adj : adjacents) {
            if (!visited[adj]) {
                dfs(graph, adj, visited, quiet, quietest);
            }
        }
    }
    private static Map<Integer, List<Integer>> buildGraph(int[][] richer) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] rich : richer) {
            if (!graph.containsKey(rich[1])) {
                List<Integer> newList = new ArrayList<>();
                newList.add(rich[0]);
                graph.put(rich[1], newList);
            } else {
                graph.get(rich[1]).add(rich[0]);
            }
        }
        return graph;
    }
}

@@ -61,60 +61,12 @@
 til.
-HashMap;%0Aimport java.util.List;%0Aimport java.util.Map
+List
 ;%0A%0A/
@@ -209,37 +209,24 @@
 t) %7B%0A       
- Map%3CInteger,
  List%3CIntege
@@ -219,33 +219,34 @@
    List%3CInteger%3E
-%3E
+%5B%5D
  graph = buildGr
@@ -255,16 +255,30 @@
 h(richer
+, quiet.length
 );%0A     
@@ -760,29 +760,16 @@
 oid dfs(
-Map%3CInteger, 
 List%3CInt
@@ -769,25 +769,26 @@
 ist%3CInteger%3E
-%3E
+%5B%5D
  graph,%0A    
@@ -1173,20 +1173,16 @@
 raph
-.get(
+%5B
 source
-)
+%5D
 ;%0A  
@@ -1396,24 +1396,25 @@
     %7D%0A    %7D%0A
+%0A
     private 
@@ -1419,29 +1419,16 @@
 e static
- Map%3CInteger,
  List%3CIn
@@ -1433,17 +1433,18 @@
 Integer%3E
-%3E
+%5B%5D
  buildGr
@@ -1457,24 +1457,34 @@
 t%5B%5D%5B%5D richer
+, int size
 ) %7B%0A        
@@ -1486,21 +1486,8 @@
     
- Map%3CInteger,
  Lis
@@ -1496,17 +1496,18 @@
 Integer%3E
-%3E
+%5B%5D
  graph =
@@ -1515,19 +1515,18 @@
 new 
-HashMap%3C%3E()
+List%5Bsize%5D
 ;%0A  
@@ -1579,35 +1579,30 @@
 if (
-!
 graph
-.containsKey(rich%5B1%5D)
+%5Brich%5B1%5D%5D == null
 ) %7B%0A
@@ -1723,29 +1723,27 @@
 raph
-.put(
+%5B
 rich%5B1%5D
-,
+%5D =
  newList
 );%0A 
@@ -1738,17 +1738,16 @@
  newList
-)
 ;%0A      
@@ -1786,21 +1786,17 @@
 raph
-.get(
+%5B
 rich%5B1%5D
-)
+%5D
 .add

Update problem 851