[Python3] Simple BFS solution with explanation
The key idea is to recognize that the given graph is directed and it may not be possible to visit every node starting from 0. In order to traverse the graph, we
The key idea is to recognize that the given graph is directed and it may not be possible to visit every node starting from 0. In order to traverse the graph, we need to make sure that every node is reachable from 0.\n\nSo turn the graph into an undirected one while noting down the original direction. Here, I have used a variable called cost. If the original direction was from source to destination, we need to reverse it and this has a cost of 1 and 0 otherwise. Perform BFS starting from 0 and add the cost to the result.\n\n```\nfrom collections import defaultdict, deque\n\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        graph = defaultdict(list)\n        for src, dest in connections:\n            graph[src].append((dest, 1))\n            graph[dest].append((src, 0))\n        \n        q = deque([0])\n        visited = set([0])\n        num_changes = 0\n        \n        while q:\n            curr = q.popleft()\n            for child, cost in graph[curr]:\n                if child not in visited:\n                    visited.add(child)\n                    num_changes += cost\n                    q.append(child)\n                    \n        return num_changes\n```
['Breadth-First Search', 'Graph', 'Python']