DFS (with explanation)
Approach\nThis solution uses a depth-first search (DFS) algorithm to determine the minimum number of edges that need to be changed to direct each city towards c
# Approach\nThis solution uses a depth-first search (DFS) algorithm to determine the minimum number of edges that need to be changed to direct each city towards city 0. Here is an overview of the approach:\n\n1. **Building the Graph**: The function first constructs a graph representation using an adjacency list. For each connection (road) between cities u and v, two entries are added to the adjacency list: one indicating a road from u to v with a direction of 1, and the other indicating a reverse road from v to u with a direction of 0.\n2. **Depth-First Search (DFS)**: The function then performs a DFS traversal starting from city 0 (the capital city) to count the number of edges that need to be changed. The dfs function recursively visits each city\'s neighbors, tracking the direction of the edges and incrementing the change_count based on the direction of the edge.\n3. **Counting Edge Changes**: At each step in the DFS traversal, the algorithm checks if the neighbor being visited is not the parent node to avoid revisiting the parent node. It then increments the change_count based on whether the edge needs to be changed (0 for reverse road, 1 for normal road).\n4. **Returning the Result**: The function returns the final count of edge changes needed to direct each city towards city 0 after completing the DFS traversal.\n\n# Complexity\n- Time complexity:\n$$O(n)$$, where n is the number of cities in the network. This complexity arises from the DFS traversal that visits each city once and explores its neighboring cities. Since the network is represented as a tree, the DFS traversal will have a maximum of n nodes to visit.\n\n- Space complexity:\n$$O(n)$$, where n is the number of cities in the network. This space is primarily used for storing the adjacency list representation of the graph, which can have up to n nodes in the case of a fully connected tree. Additionally, the recursive DFS function consumes space on the call stack proportional to the depth of the tree, which can be up to n in the worst case for a linear tree structure.\n\n# Code\n``` python3 []\nclass Solution:\n    def minReorder(self, n: int, connections: List[List[int]]) -> int:\n        graph = defaultdict(list)\n\n        for u, v in connections:\n            # Road from u to v\n            graph[u].append((v, 1))\n            # Reverse road from v to u\n            graph[v].append((u, 0))\n\n        def dfs(node, parent):\n            change_count = 0\n            for neighbor, direction in graph[node]:\n                if neighbor != parent:\n                    # Count the edges that need to be changed\n                    change_count += direction\n                    change_count += dfs(neighbor, node)\n            return change_count\n\n        return dfs(0, -1)\n```\n``` javascript []\n/**\n * @param {number} n\n * @param {number[][]} connections\n * @return {number}\n */\nvar minReorder = function(n, connections) {\n    const graph = new Array(n).fill(null).map(() => []);\n    \n    for (const [u, v] of connections) {\n        // Road from u to v\n        graph[u].push([v, 1]);\n        // Reverse road from v to u\n        graph[v].push([u, 0]);\n    }\n\n    function dfs(node, parent) {\n        let changeCount = 0;\n        for (const [neighbor, direction] of graph[node]) {\n            if (neighbor !== parent) {\n                // Count the edges that need to be changed\n                changeCount += direction;\n                changeCount += dfs(neighbor, node);\n            }\n        }\n        return changeCount;\n    }\n\n    return dfs(0, -1);\n};\n```\n``` php []\nclass Solution {\n    function dfs($node, $parent, $graph) {\n        $changeCount = 0;\n        foreach ($graph[$node] as list($neighbor, $direction)) {\n            if ($neighbor !== $parent) {\n                // Count the edges that need to be changed\n                $changeCount += $direction;\n                $changeCount += $this->dfs($neighbor, $node, $graph);\n            }\n        }\n        return $changeCount;\n    }\n\n    /**\n     * @param Integer $n\n     * @param Integer[][] $connections\n     * @return Integer\n     */\n    function minReorder($n, $connections) {\n        $graph = array_fill(0, $n, []);\n    \n        foreach ($connections as $connection) {\n            list($u, $v) = $connection;\n            // Road from u to v\n            $graph[$u][] = [$v, 1];\n            // Reverse road from v to u\n            $graph[$v][] = [$u, 0];\n        }\n\n        return $this->dfs(0, -1, $graph);\n    }\n}\n```
['Depth-First Search', 'PHP', 'Python3', 'JavaScript']