Reorder Routes to Make All Paths Lead to City Zero

1package pkg5leetcode.official75;2 3/*4 * Reorder Routes to Make All Paths Lead to City Zero | LC 14665 * APPROACH: BFS/DFS tree from 0; count wrong-direction edges.6 * COMPLEXITY: Time O(n), Space O(n)7 */8import java.util.*;9 10public class official75_LC1466ReorderRoutesToMakeAllPathsLeadToCityZero {11    static int minReorder(int n, int[][] connections) {12        List<List<int[]>> adj = new ArrayList<>();13        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());14        for (int[] c : connections)15            adj.get(c[0]).add(new int[]{c[1], 1});16        for (int[] c : connections)17            adj.get(c[1]).add(new int[]{c[0], 0});18        boolean[] seen = new boolean[n];19        Deque<int[]> q = new ArrayDeque<>();20        q.add(new int[]{0, 0});21        seen[0] = true;22        int flips = 0;23        while (!q.isEmpty()) {24            int[] cur = q.poll();25            for (int[] e : adj.get(cur[0])) {26                if (seen[e[0]]) continue;27                seen[e[0]] = true;28                flips += e[1];29                q.add(new int[]{e[0], 0});30            }31        }32        return flips;33    }34 35    public static void main(String[] args) {36        check(minReorder(6, new int[][]{{0,1},{1,3},{2,3},{4,0},{4,5}}) == 3, "case1");37        check(minReorder(5, new int[][]{{1,0},{1,2},{3,2},{3,4}}) == 2, "case2");38        System.out.println("all tests passed");39    }40 41    static void check(boolean cond, String name) {42        if (!cond) throw new AssertionError("FAILED: " + name);43        System.out.println("  PASS " + name);44    }45}