Java | DFS | Clean code | O(n) time
Intuition\n Describe your first thoughts on how to solve this problem. \nSince there are n cities and n-1 roads, and the graph is connected, there are bound to 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nSince there are `n` cities and `n-1` roads, and the graph is connected, there are bound to be no cycles in the graph. We can construct an adjacency list of the roads assuming they are bidirectional, but remembering the order of the roads in the list. Now we can run a DFS traversal starting from city 0 and visit all other cities. During the traversal we can count the number of roads that need to be re-ordered.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n  List<Pair<Integer, Boolean>>[] adj;\n  int cnt = 0;\n\n  private void dfs(int city, int parent) {\n    for (var a : adj[city]) {\n      var neighbor = a.getKey();\n      var needsReOrder = a.getValue();\n\n      if (neighbor != parent) {\n        if (needsReOrder) cnt++;\n        dfs(neighbor, city);\n      }\n    }\n  }\n\n  public int minReorder(int n, int[][] connections) {\n    adj = new ArrayList[n];\n\n    for (var i=0; i<n; i++)\n      adj[i] = new ArrayList<>();\n\n    for (var con : connections) {\n      adj[con[0]].add(new Pair(con[1], true));\n      adj[con[1]].add(new Pair(con[0], false));\n    }\n    dfs(0, -1);\n\n    return cnt;\n  }\n}\n```\nIf you like my solution, please upvote it!
['Depth-First Search', 'Graph', 'Recursion', 'Java']