Problem Description

The problem presents a directed graph representing roads between cities. The goal is to find the minimum number of road direction changes needed to ensure all cities can reach city 0 (the capital). The graph is a tree, meaning there's exactly one path between any two cities.

Solution Explanation

Both Depth-First Search (DFS) and Breadth-First Search (BFS) efficiently solve this problem. The core idea is to build an undirected graph from the input connections, and then traverse the graph from city 0, counting the number of edges that need their direction reversed to point towards city 0.

Approach:

1. Graph Representation: The input connections is used to construct an adjacency list. Each node (city) maintains a list of its neighbors, along with a flag indicating whether the edge to that neighbor is initially oriented towards or away from the current node (0 or 1, respectively).

2. Traversal: A depth-first search (DFS) or breadth-first search (BFS) algorithm starts at city 0. During the traversal, each visited edge is checked. If the edge's orientation is initially away from city 0, the counter for required direction changes is incremented.

3. Counting Changes: The traversal ensures that all reachable cities are visited. The final count represents the minimum number of edge direction changes.

Time Complexity Analysis

Both DFS and BFS solutions have a time complexity of O(N), where N is the number of cities. This is because each edge and node in the tree is visited exactly once.

Space Complexity Analysis

The space complexity for both algorithms is O(N) to store the adjacency list (graph) and the visited set (or queue in BFS). In the worst case, the recursion depth in DFS could be O(N), leading to a space complexity of O(N) for the call stack.

Code Implementation (Python)

Here's the Python code implementation using both DFS and BFS:

DFS:

from collections import deque
 
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]  # Adjacency list
 
        for u, v in connections:
            graph[u].append((v, 1))  # (neighbor, direction_flag: 1 if u->v, 0 if v->u)
            graph[v].append((u, 0))
 
        visited = set()
        changes = 0
 
        def dfs(node):
            nonlocal changes
            visited.add(node)
            for neighbor, direction in graph[node]:
                if neighbor not in visited:
                    changes += direction # Increment if initially away from city 0
                    dfs(neighbor)
 
        dfs(0)  # Start DFS from city 0
        return changes
 

BFS:

from collections import deque
 
class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]
 
        for u, v in connections:
            graph[u].append((v, 1))
            graph[v].append((u, 0))
 
        queue = deque([0])
        visited = {0}
        changes = 0
 
        while queue:
            node = queue.popleft()
            for neighbor, direction in graph[node]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append(neighbor)
                    changes += direction
 
        return changes
 

The code in other languages (Java, C++, Go, TypeScript, Rust) follows a similar structure and logic, adapting syntax and data structures as needed. The core algorithm (DFS or BFS) remains the same, with the same time and space complexities.