_1466.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.*;

publicclass_1466 {
publicstaticclassSolution1 {
publicintminReorder(intn, int[][] connections) {
// key is entering city, value is departure city
Map<Integer, Set<Integer>> map = newHashMap<>();
Queue<Integer> queue = newLinkedList<>();
intminReorder = 0;
Set<Integer> visited = newHashSet<>();
for (inti = 0; i < n; i++) {
visited.add(i);
 }

// key is departure city, value is entering city
Map<Integer, Set<Integer>> reverseMap = newHashMap<>();
for (int[] con : connections) {
if (!map.containsKey(con[1])) {
map.put(con[1], newHashSet<>());
 }
map.get(con[1]).add(con[0]);

if (!reverseMap.containsKey(con[0])) {
reverseMap.put(con[0], newHashSet<>());
 }
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()) {
intcurr = queue.poll();
visited.remove(curr);
if (map.containsKey(curr)) {
Set<Integer> departureCityList = map.get(curr);
for (intcity : departureCityList) {
if (visited.contains(city)) {
queue.offer(city);
 }
 }
 }
if (reverseMap.containsKey(curr)) {
Set<Integer> enteringCityList = reverseMap.get(curr);
for (intcity : enteringCityList) {
if (visited.contains(city)) {
queue.offer(city);
minReorder++;
 }
 }
 }
 }
returnminReorder;
 }
 }

publicstaticclassSolution2 {
/*
 * build an adjacency list and BFS
 */
publicintminReorder(intn, int[][] connections) {
// int[] in the below map holds two integers, the first one means the node, the second
// one means the direction:
// 0 means it's pointing to the key, i.e. doesn't need to be flipped,
// 1 means it's the opposite direction, i.e. needs to be flipped
Map<Integer, List<int[]>> adjList = newHashMap<>();
for (int[] conn : connections) {
adjList.computeIfAbsent(conn[0], k -> newArrayList<>())
 .add(newint[] {conn[1], 1});
adjList.computeIfAbsent(conn[1], k -> newArrayList<>())
 .add(newint[] {conn[0], 0});
 }
intcount = 0;
Queue<Integer> queue = newLinkedList<>();
queue.offer(0);
boolean[] visited = newboolean[n];
visited[0] = true;
while (!queue.isEmpty()) {
Integercurr = queue.poll();
if (!adjList.containsKey(curr)) {
continue;
 }
for (int[] next : adjList.get(curr)) {
intneighbor = next[0];
intflip = next[1];
if (!visited[neighbor]) {
count += flip;
visited[neighbor] = true;
queue.offer(neighbor);
 }
 }
 }
returncount;
 }
 }
}