Python | BFS | DFS | Graphs | Easy to Understand
Approach: Create a graph with both original edges and their reversed counterparts (with scores 1 and 0, respectively).  Traverse the graph starting from node \'
**Approach:** Create a graph with both original edges and their reversed counterparts (with scores 1 and 0, respectively).  Traverse the graph starting from node \'0\', incrementing a count for each original edge that points away from node \'0\'. This count represents the necessary reorientations.\nBelow code provides explanations through comments.\n\n**Please Feel free to suggest optimizations!**\n\n### **Python Solution:**\n\n**BFS -- Beats 95%**\n```\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        """ BFS """\n        # Construct graph\n        graph = defaultdict(dict)\n        for a, b in connections:\n            graph[a][b] = 1    # Original Edge with score 1\n            graph[b][a] = 0    # Fake edge with score 0\n        \n        # Initialize a deque with start node as 0\n        queue = deque([0,])\n        wrong_edges = 0        # Keeps track of the edges away from \'0\'\n        visited = [False] * n  # Avoids cyclic traversal\n        visited[0] = True      # Mark 0 as visited since we start from it\n        \n        # BFS Traversal\n        while queue:\n            start = queue.popleft()\n            for nei, score in graph[start].items():\n                if not visited[nei]:\n                    # When the original edge is towards \'0\' then score is 0 otherwise 1\n                    wrong_edges += score\n                    queue.append(nei)\n                    visited[nei] = True\n        \n        return wrong_edges\n```\n**DFS**\n```\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        graph = defaultdict(set)\n        for a, b in connections:\n            graph[a].add((b, 1))    # Original Edge\n            graph[b].add((a, 0))    # Fake Edge to enable complete tree traversal\n        \n        # DFS to traverse over the edges and\n        # increment self.count when an edge directs away from \'0\'\n        def dfs(start):\n            for nei, is_real in graph[start]:\n                if not visited[nei]:\n                    self.count += is_real\n                    visited[nei] = True\n                    dfs(nei)\n        \n        # To avoid visiting the same node again\n        visited = [False] * n\n        # Mark the first node as visited\n        visited[0] = True\n        # To keep track of edges that go away from \'0\'\n        self.count = 0\n        \n        # Start traversing the graph from \'0\'\n        dfs(0)\n        \n        return self.count\n```
['Depth-First Search', 'Breadth-First Search', 'Graph', 'Python3']