[2 Minute Read] Easy BFS
The trick we are going to apply here is that we would add some extra edges to our given Tree (if you are thinking, how it\'s a tree, then a graph having n nodes
The trick we are going to apply here is that we would add some extra edges to our given Tree (if you are thinking, how it\'s a tree, then a graph having `n` nodes and `n - 1` edges such that there is only one path between any 2 pair of vertices is sure to be a Tree). \n\n**The TRICK**\n1. Reverse the direction of edges in which it\'s originally given.\n2. For every edge of step 1, add it\'s reverse also, and mark it somehow so it\'s identifiable differently. (Let\'s call it `artificial` edge)\n\n**Algorithm**\n1. Maintain a `count` variable.\n2. Start BFS from node `0` and visit every node of the graph.\n3. If to visit a node, you use an `artificial` edge, increase your count by `1`.\n\n<br>\n\n**CONTEXT**\n- Firstly, we are storing the edges in a reverse order than that giving by `connections` because we wan\'t to be able to be able to reach from node `0` to every other node, since simulating the process of reaching from one node to every other node is easier than simulating to reach from every other node to `0` (which is demanded in the problem). \n- Secondly, we add a reverse edge for every edge which we added in the first step, to make sure that if there is an edge from, say node `a` to node `b`, then we now also have an edge from `b` to `a`, which helps us simulate as if we are rotating an edge. It signifies that if we choose the former edge, then we are not rotating this edge, but if we choose the latter one, then we are rotating this edge. Also, to recognize the latter edge we can use a `boolean` value to signify if it\'s an `artificial` edge or not.\n- Thirdly, we perform a Simple BFS, starting from node `0`, and move to the next node iteratively level by level, using the edge taking us from the current node to the next node. If this edge is a normal one, then we would simply continue with our BFS. If this edge is an `artificial` edge, then we would increase our `count` by `1`, and then continue with our BFS.\n\n<br>\n\nBelow is the code for the above algorithm in JAVA.\n\n```java\nclass Solution {\n\n\t// custom class for keeping the destination from a source \n    class Dest {\n        int v;\n\t\tboolean artificial;     // true if this edge was added artificially and was not in the original Tree\n        public Dest(int v, boolean artificial) {\n            this.v = v;\n            this.artificial = artificial;\n        }\n    }\n    public int minReorder(int n, int[][] connections) {\n        Map<Integer, ArrayList<Dest>> map = new HashMap<>();\n        for(int i = 0; i < n; i++) {\n            map.put(i, new ArrayList<>());\n        }\n        for(int e[] : connections) {\n            int u = e[0], v = e[1];\n            map.get(v).add(new Dest(u, false));\n            map.get(u).add(new Dest(v, true));\n        }\n        \n        int cost = 0;\n        Queue<Integer> q = new LinkedList<>();\n        q.add(0);\n        boolean visited[] = new boolean[n];\n        visited[0] = true;\n        while(!q.isEmpty()) {\n            int temp = q.poll();\n            for(Dest i : map.get(temp)) {\n                if(visited[i.v]) continue;\n                if(i.artificial) cost++;    // if this is the artificially added node, then increase cost\n                q.add(i.v);\n                visited[i.v] = true;\n            }\n        }\n        return cost;\n    }\n}\n```
['Breadth-First Search', 'Java']