Minimalist Explanation | Python | DFS | Recursion
\n# Approach\n1. Construct Adjacency list graph\n2. Create a list visited of size n where all the values are False initially as we have not visited any of the n
\n# Approach\n1. Construct Adjacency list `graph`\n2. Create a list `visited` of size `n` where all the values are `False` initially as we have not visited any of the nodes yet.\n3. Traverse using DFS to reach to the apples recursively.\n4. During traversal, mark the visited nodes to `True` otherwise you will end up getting `Maximum Recursion Depth Exceeded` due to the endless cycle.\n5. Calculate the `total` which is the minimum time required. (Added the logic explaination in comments)\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(N)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(N)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def bfs(self, graph, sv, hasApple, visited):\n        # sv - starting vertex\n\n        # visited - list of visited nodes\n        # initially all are filled False\n        total = 0\n        visited[sv] = True\n        for i in graph[sv]:\n            if not visited[i]:\n                total += self.bfs(graph, i, hasApple, visited)\n        \n        # we are adding 2 to total becoz, for finding an apple,\n        # we are traversing via an edge from top to vertex and\n        # again reverse to top to starting vertex.\n\n        # starting vertex i.e 0th node has no contribution in finding an apple,\n        # so we exclude it when calculating total - (sv != 0)\n\n        # total>0 becoz in 1st example consider node 1, although\n        # it does not have an apple, its child 4 has an apple\n        # and it is contributing it carry forwarding 2 to 0th node\n        # so such cases are also included - (total>0)\n        if((total>0 or hasApple[sv]) and sv!=0):\n            total += 2\n        return total\n\n    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:\n        graph = defaultdict(list)\n        visited = [False]*n # visited nodes\n        for x,y in edges:\n            graph[x].append(y)\n            graph[y].append(x)\n        total = self.bfs(graph, 0, hasApple, visited)\n        return total\n```
['Python', 'Python3']