add 1466

fishercoder1534 · fishercoder1534 · commit e8ea4368fff5 · 2020-06-01T07:30:03.000-07:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1466|[Reorder Routes to Make All Paths Lead to the City Zero](https://leetcode.com/problems/reorder-routes-to-make-all-paths-lead-to-the-city-zero/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1466.java) | |Medium|Tree, DFS|
 |1464|[Maximum Product of Two Elements in an Array](https://leetcode.com/problems/maximum-product-of-two-elements-in-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1464.java) | |Easy|Array|
 |1460|[Make Two Arrays Equal by Reversing Sub-arrays](https://leetcode.com/problems/make-two-arrays-equal-by-reversing-sub-arrays/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1460.java) | |Easy|Array|
 |1457|[Pseudo-Palindromic Paths in a Binary Tree](https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1457.java) | |Medium|Bit Manipulation, Tree, DFS|
diff --git a/src/main/java/com/fishercoder/solutions/_1466.java b/src/main/java/com/fishercoder/solutions/_1466.java
@@ -0,0 +1,72 @@
+package com.fishercoder.solutions;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Set;
+
+public class _1466 {
+    public static class Solution1 {
+        public int minReorder(int n, int[][] connections) {
+            //key is entering city, value is departure city
+            Map<Integer, Set<Integer>> map = new HashMap<>();
+            Queue<Integer> queue = new LinkedList<>();
+            int minReorder = 0;
+            Set<Integer> visited = new HashSet<>();
+            for (int i = 0; i < n; i++) {
+                visited.add(i);
+            }
+
+            //key is departure city, value is entering city
+            Map<Integer, Set<Integer>> reverseMap = new HashMap<>();
+            for (int[] con : connections) {
+                if (!map.containsKey(con[1])) {
+                    map.put(con[1], new HashSet<>());
+                }
+                map.get(con[1]).add(con[0]);
+
+                if (!reverseMap.containsKey(con[0])) {
+                    reverseMap.put(con[0], new HashSet<>());
+                }
+                reverseMap.get(con[0]).add(con[1]);
+
+                //for all those directly connected to city 0, must be reordered if not yet
+                //and they are the start nodes of BFS
+                if (con[0] == 0) {
+                    minReorder++;
+                    queue.offer(con[1]);
+                    visited.remove(con[1]);
+                    visited.remove(0);
+                }
+                if (con[1] == 0) {
+                    queue.offer(con[0]);
+                    visited.remove(0);
+                }
+            }
+            while (!queue.isEmpty() || !visited.isEmpty()) {
+                int curr = queue.poll();
+                visited.remove(curr);
+                if (map.containsKey(curr)) {
+                    Set<Integer> departureCityList = map.get(curr);
+                    for (int city : departureCityList) {
+                        if (visited.contains(city)) {
+                            queue.offer(city);
+                        }
+                    }
+                }
+                if (reverseMap.containsKey(curr)) {
+                    Set<Integer> enteringCityList = reverseMap.get(curr);
+                    for (int city : enteringCityList) {
+                        if (visited.contains(city)) {
+                            queue.offer(city);
+                            minReorder++;
+                        }
+                    }
+                }
+            }
+            return minReorder;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1466Test.java b/src/test/java/com/fishercoder/_1466Test.java
@@ -0,0 +1,26 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._1466;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _1466Test {
+    private static _1466.Solution1 solution1;
+    private static int[][] connections;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1466.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        connections = new int[][]{
+                {0, 1}, {1, 3}, {2, 3}, {4, 0}, {4, 5}
+        };
+        assertEquals(3, solution1.minReorder(6, connections));
+    }
+
+}
