Java Level-Order Traversal Solution Using BFS with Detailed Explanations
Intuition\nWhen should we change the direction of a route? If the route starts from a city close to city 0 and ends at a city far from city 0, we need to change
# Intuition\nWhen should we change the direction of a route? If the route starts from a city close to city 0 and ends at a city far from city 0, we need to change its direction since it brings people "away" from city 0. Otherwise we don\'t need to change its direction since it already meets our need. In this case, once we get the distance from each city to city 0, we can run a simple iteration to count the number of routes that needs to be changed.\n\nTo get the distance from each city to city 0, we can traverse the associated undirected graph in the level order using breath-first search (BFS).\n\n# Approach\nThe algorithm is as follows.\n1. Create the adjacency list representation of the associated undirected graph.\n2. Initialize the adjacent list by iterate over all the edges `connections`.\n3. Conduct BFS on the undirected graph in the level order, starting from city 0. Update `distToZero` during the traversal.\n4. Initialize the counter `ans` for final output. Iterate over `connections` again, if `distToZero[e[0]] < distToZero[e[1]]`, this edge leads away from city 0 so we need to increment the counter `ans`.\n5. Return `ans` as the final result.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n\n```\nclass Solution {\n    public int minReorder(int n, int[][] connections) {\n        // BFS Approach\n        // TC: O(n), SC: O(n)\n        // distToZero[i] = distance from city i to city 0\n        int[] distToZero = new int[n];\n        List<List<Integer>> adjList = new ArrayList<>();\n        for (int i = 0; i < n; i++) {\n            adjList.add(new ArrayList<>());\n        }\n        for (int[] e : connections) {\n            adjList.get(e[0]).add(e[1]);\n            adjList.get(e[1]).add(e[0]);\n        }\n        // BFS\n        Queue<Integer> queue = new ArrayDeque<>();\n        queue.offer(0);\n        boolean[] visited = new boolean[n];\n        visited[0] = true;\n        int dist = 0;\n        while (!queue.isEmpty()) {\n            int size = queue.size();\n            for (int i = 0; i < size; i++) {\n                int curr = queue.poll();\n                distToZero[curr] = dist;\n                for (int nei : adjList.get(curr)) {\n                    if (!visited[nei]) {\n                        queue.offer(nei);\n                        visited[nei] = true;\n                    }\n                }\n            }\n            dist++;\n        }\n        int ans = 0;\n        for (int[] e : connections) {\n            // If the edge directs from near to far, we change the direction\n            if (distToZero[e[0]] < distToZero[e[1]]) {\n                ans++;\n            }\n        }\n        return ans;\n        \n    }\n}\n```
['Tree', 'Breadth-First Search', 'Graph', 'Queue', 'Java']