[Python3] Simple DFS Solution. No set required, faster than 92%.
To start we create out grid:\n\ngrid = defaultdict(list)\nfor a, b in connections:\n    grid[a].append((b, 1))\n    grid[b].append((a, 0))\n\nFor each connectio
To start we create out grid:\n```\ngrid = defaultdict(list)\nfor a, b in connections:\n    grid[a].append((b, 1))\n    grid[b].append((a, 0))\n```\nFor each connection we have, there is a road from A to B. We add a road in both directions, so to speak, but store the direction in the second element of the tuple, with 1 meaning we are travelling in the same direction as the road, and 0 meaning we are pathing the opposite direction.\n\nNext we have our depth first search, which we will start at 0/ the capital city:\n```\ndef dfs(location, parent):\n    ans = 0\n    for connection, direction in grid[location]:\n        if connection == parent: continue\n        ans += direction + dfs(connection, location)\n    return ans\n```\nWe path through each road at our location in the grid, we avoid backtracking through the same path as our parent. This is sufficient as opposed to a visited variable, as due to the fact that there are n - 1 roads, there are no loops and only one way to path through the entire graph.\n\nAs we start our dfs at the capital/ node 0, if we travel down any road in its intended direction, it is pointed/ travelling away from the capital, thus needs to be flipped, so we add 1 to our answer. If we travel down a road in the other direction than its intended one, it is orientated before the capital and we can ignore it.\n\nThus now we just need to start our dfs at 0 and return the answer.\n```\nreturn dfs(0, -1)\n```\n# Solution\n```\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        grid = defaultdict(list)\n        for a, b in connections:\n            grid[a].append((b, 1))\n            grid[b].append((a, 0))\n\n        def dfs(location, parent):\n            ans = 0\n            for connection, direction in grid[location]:\n                if connection == parent: continue\n                ans += direction + dfs(connection, location)\n            return ans\n        return dfs(0, -1)\n\n```\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$
['Depth-First Search', 'Python3']