Java O(n) dfs with explanation
Explanation: Since the problem states that we will always have n-1 connections and we will always be able to reorder so that every city can reach 0, we can conc
Explanation: Since the problem states that we will always have `n-1` connections and we will always be able to reorder so that every city can reach 0, we can conclude that no cycles will exist. If you are not conviced, try to think about a case where you have `n-1` edges and a cycle. You will notice that if you do that, you will make some cities unable to reach the city 0 even after reordering.\n\nHaving this in mind, you can use the following approach to calculate the answer:\n1. Transform each edge in a bi-directional edge, so that when you go on the right (original) direction, it costs you 1, and when you go on the not original direction, it costs you 0.\n2. Start a dfs from city 0 and go to its neighbors, and always add the cost of going to that direction.\n3. Because of what you did on (1), if the direction is correct, it means that that edge needs to be reversed, hence it will cost one.\n\nCommented code presented below. Complexity is O(n).\n\n```\nclass Solution {\n    public int minReorder(int n, int[][] connections) {\n\t\t//ajdacency list where int[] will be [dest,cost]\n        List<int[]>[] cons = new List[n];\n        for(int[] con : connections) {\n            if (cons[con[0]] == null) cons[con[0]] = new ArrayList<int[]>();\n            if (cons[con[1]] == null) cons[con[1]] = new ArrayList<int[]>();\n            cons[con[0]].add(new int[]{con[1],1});//original direction, costs 1\n            cons[con[1]].add(new int[]{con[0],0});//oposite directions, costs 0\n        }\n        return dfs(0,cons,new boolean[n]);\n    }\n    private int dfs(int curr, List<int[]>[] cons, boolean[] visited) {\n        int cost = 0;\n        visited[curr]=true;\n        for(int[] neigh : cons[curr]) {\n            if (!visited[neigh[0]]) {\n                cost += neigh[1];\n                cost += dfs(neigh[0],cons,visited);\n            }\n        }\n        return cost;\n    }\n}\n```
[]