Visual Explanation | Simple Python DFS Solution | Idea | Comments
\n\nThought Process ...\n We want all directions towards city 0\n We know that we can reach to every city from 0 if its bidirectional\n Then we assume that we v
![image](https://assets.leetcode.com/users/images/eea7bb30-0a27-4665-b6e1-4457bef2fb75_1638852748.6979036.png)\n\n**Thought Process ...**\n* We want all directions towards city 0\n* We know that we can reach to every city from 0 if its bidirectional\n* Then we assume that we visit every city starting from 0, and whenever direction toward to visiting city from 0 is equal to the given direction from input -> meaning that we need to swap the direction\n* total number of needs of swapping of direction is what the problem is looking for\n\n**Approach ...**\n* Let\'s build our own \'undirected\' graph so we can travel from 0 to all cities (from left to right on the image)\n* While we build our graph, let\'s mark down if the direction from 0 is equal to the direction given by the input with True or False (T, F marks on the image)\n* let us make sure that we mark down the visited cities so we don\'t go backward\n* When we traverse our \'undirected\' graph DFS, if the path I am using is same as the given input (which in this case True) and count the number of paths that we need to invert. (because we are traversing from 0 to cities, and problem want all cities can travel to 0)\n\n**Time and Space Complexity ... -> O(n), O(n)**\n* We visit all cities only once; therefore, time complexity -> O(n) where n is number of cities. (notice we can ignore the number of path because number of path is always n-1 in this problem)\n* We use space to build graph, recursive call stack, and visited set. All are O(n); therefore, O(3n) -> O(n)\n\n```\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        graph = defaultdict(list)\n        visited = set()\n        # building undirected graph\n        for s, e in connections:\n            graph[s].append((e, True))\n            graph[e].append((s, False))\n        \n        def dfs(currCity):\n            count = 0\n            if currCity in visited:\n                return\n            visited.add(currCity)\n            for neigh, orig in graph[currCity]:\n                if neigh not in visited:\n\t\t\t\t\t# if current path is same as original path that were given from input, \n\t\t\t\t\t# we know that we need to invert the path\n                    if orig == True:\n                        count += 1\n                    count += dfs(neigh)\n            return count\n\t\t\t\n        return dfs(0)\n```\n**Please correct me if I am wrong !\nPlease UPVOTE if you find this solution helpful !\nHappy algo!**
['Depth-First Search', 'Python']