Python | BFS | Directed Graph + Undirected Graph | Explained with comments
\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        from collections import defaultdict\n        \n        undire
```\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        from collections import defaultdict\n        \n        undirected_graph = defaultdict(list)\n        actual_graph = defaultdict(set)  # for faster lookup\n\n        for a,b in connections:\n            undirected_graph[a].append(b) #Figure out which cities are connected to each other (i.e a road exists between the two) \n            undirected_graph[b].append(a)\n            actual_graph[a].add(b)  #Figure out which cities have "valid" roads (i.e you are allowed to go from a to b)\n\n        queue = [(node, 0) for node in undirected_graph[0]] #All neighbours of 0 #(node, destination_node) \n        res = 0\n        visited = set([0])# Mark 0 as visited\n        \n        while queue:\n            node, destination_node = queue.pop()\n            visited.add(node) #Mark node as visited \n\n            if not (destination_node in actual_graph[node]):   #If there is no "valid" road which lets you travel from node to destination_node, you\'ll have to reverse the road\n                res += 1\n\n            for neighb in undirected_graph[node]: #For all unvisited neighbours, you\'ll have to continue exploring\n                if neighb not in visited:\n                    queue.append((neighb, node))\n        \n        return res\n```\n\nTime: O(N)\nSpace: O(N)\n\nYou\'ll have to explore all N-1 edges to make the graphs anyway\nWorst case, you\'ll have to store all nodes (except 0) in the queue.
['Breadth-First Search', 'Graph', 'Python']