Easy & Clear Solution Python 3
Intuition\nThe problem requires us to reorient some edges in a tree such that all cities can visit the capital city, and we need to return the minimum number of
# Intuition\nThe problem requires us to reorient some edges in a tree such that all cities can visit the capital city, and we need to return the minimum number of edges that need to be changed. To solve this, we can use a DFS algorithm to traverse the tree and count the number of edges that need to be reversed.\n# Approach\nYour code initializes an empty adjacency list adj with n empty lists for each node in the graph. Then, it populates the adjacency list with the edges given in the connections list by adding the destination node with a value of 1 to the source node\'s list and adding the source node with a value of 0 to the destination node\'s list. Here, the value of 1 indicates that the edge needs to be reversed to reach the capital city, and 0 indicates that it doesn\'t need to be reversed.\n\nAfter setting up the adjacency list, the code implements a depth-first search algorithm dfs to traverse the tree. The dfs function takes two parameters: child and parent, where child represents the current node being traversed, and parent represents the parent of the current node.\n\nIn the dfs function, we iterate through each child node of the current node in the adjacency list. If the child node is not the parent node, it means that we need to reverse the edge between the current node and the child node. We increment the res variable by 1 if the value of the edge is 1, indicating that it needs to be reversed. Then, we call the dfs function recursively with the child node as the new current node and the current node as the new parent node.\n\nFinally, the code calls the dfs function with the capital city (node 0) as the current node and -1 as the parent node to start the traversal. It returns the res variable, which holds the number of edges that need to be reversed to reach the capital city.\n\n# Complexity\n- Time complexity:\nThe code iterates through each node in the tree once, so the time complexity is O(n), where n is the number of nodes in the tree.\n\n- Space complexity:\nThe code uses an adjacency list to store the edges, which takes O(n) space. The DFS algorithm uses a recursive stack, which can have at most n nodes in the worst case, so the space complexity is O(n). Overall, the space complexity of the code is O(n).\n\n# Code\n```\nclass Solution:\n    res=0\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        adj=[]\n        for i in range(n):\n            adj.append([])\n        for i in connections:\n            adj[i[0]].append([i[1],1])\n            adj[i[1]].append([i[0],0])\n        def dfs(child,parent):\n            for [c, s] in adj[child]:\n                if c!=parent:\n                    self.res+=s\n                    dfs(c,child)\n        dfs(0,-1)\n        return self.res\n          \n\n```
['Python3']