[Python][Explanation] Approach with "virtual" nodes beats 85% with DFS
Okay, we have to reorient the roads for making our event successful. Let\'s go!\n\nFirst of all, let\'s think about the building graph and traversal. \n\nQ & A:
Okay, we have to reorient the roads for making our event successful. Let\'s go!\n\nFirst of all, let\'s think about the building graph and traversal. \n\n**Q & A:**\n\nQ: How will we traverse this one?\nA: Let\'s build connections in opposite direction!\n\nQ: What the traversal will give us?\nA: We will able to reach out to all nodes and count nodes that we added.\n\n**Stop.**\n\nQ: How will we understand that node has been added by us? \nA: Let\'s mark such nodes as "virtual" during building the graph.\n\nOkay, so we just need to make a DFS and compare if the connection between the current node and prev is virtual?\nYes! Just increment your counter, dude.\n\nTC: O(V + E) for DFS\nSC: O(V + E) for graph + O(E) for making opposite connections\n\n```\nclass Solution:\n    \n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        if not connections: return 0\n        \n        graph = collections.defaultdict(dict)\n        \n        for fr,to in connections:\n            graph[fr][to] = \'existing\'\n            graph[to][fr] = \'virtual\'\n        \n        visited = [False] * n\n        \n        self.result = 0\n        \n        self.dfs(graph, 0, -1, visited)\n        \n        return self.result\n\n    def dfs(self, graph, vertex, prev, visited):\n        visited[vertex] = True\n        \n        if graph[vertex].get(prev, \'N/A\') == \'virtual\':\n            self.result += 1\n        \n        for nei, type in graph[vertex].items():\n            if not visited[nei]:\n                self.dfs(graph, nei, vertex, visited)\n```
[]