Problem Description

You are given n cities numbered from 0 to n - 1 connected by n - 1 one-way roads, forming a tree structure where there's exactly one path between any two cities. The roads are represented by a list called connections, where each connections[i] = [ai, bi] indicates a directed road from city ai to city bi.

There's going to be a big event in the capital city (city 0), and people from all other cities need to be able to travel to city 0. However, due to the current direction of the roads, not all cities can reach the capital.

Your task is to find the minimum number of roads whose directions need to be reversed so that every city can reach city 0.

For example, if you have roads 0→1, 0→2, and 3→2, cities 1 and 2 can't reach city 0 because the roads point away from it. You'd need to reverse the directions of roads 0→1 and 0→2 to make them 1→0 and 2→0. City 3 can already reach city 0 through city 2 (following the path 3→2 then 2→0 after reversal), so you need to change 2 road directions in total.

The problem guarantees that the cities and roads form a valid tree structure, meaning there's always a solution where every city can reach city 0 after some reorientations.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem explicitly involves cities (nodes) connected by roads (edges), forming a network structure. We have n cities and n-1 roads connecting them.

Is it a tree?

• Yes: The problem states there are n cities and n-1 roads with exactly one way to travel between any two cities. This is the definition of a tree - a connected graph with no cycles. The problem even explicitly mentions "this network forms a tree."

DFS

• Following the flowchart, when we have a tree structure, the natural algorithm choice is DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS for this problem. This makes perfect sense because:

1. We need to traverse a tree structure starting from city 0
2. We need to visit all nodes and check the direction of edges along the way
3. DFS allows us to systematically explore all paths from the root (city 0) to all other cities
4. During the DFS traversal, we can count how many edges need to be reversed (those pointing away from city 0 in our traversal direction)

The DFS approach perfectly matches the solution where we start from city 0 and traverse to all other cities, counting the edges that need reversal along the way.

Intuition

The key insight is to think about this problem from a different perspective. Instead of trying to make all cities reach city 0, we can flip our thinking: start from city 0 and try to reach all other cities. This mental flip simplifies the problem significantly.

Since we have a tree structure (n cities with n-1 roads), we know that there's exactly one path between any two cities. This means if we can traverse from city 0 to all other cities, we just need to count how many roads are pointing in the "wrong" direction during our traversal.

Consider what happens when we perform DFS from city 0:

• If we encounter a road from city a to city b in our original connections, and we're traversing from a to b, the road is already pointing the wrong way (away from city 0). We need to reverse it.
• If we're traversing from b to a, the road is pointing the right way (toward city 0). No reversal needed.

To implement this, we can build an undirected graph representation but mark each edge with whether it needs reversal:

• For each original directed edge [a, b], we add both (a→b, cost=1) and (b→a, cost=0) to our graph
• The cost of 1 means we need to reverse the original edge if we traverse it in that direction
• The cost of 0 means the original edge already points in the right direction

When we DFS from city 0, we sum up all the costs of edges we traverse. This gives us the minimum number of reversals needed because:

1. We visit every city exactly once (tree property)
2. Each edge we traverse either needs reversal (cost=1) or doesn't (cost=0)
3. The sum of costs equals the total number of reversals required

This approach elegantly transforms a seemingly complex reorientation problem into a simple graph traversal with edge weights representing reversal costs.

Learn more about Depth-First Search, Breadth-First Search and Graph patterns.

Solution Approach

The implementation uses DFS with an adjacency list representation of the graph. Let's walk through the solution step by step:

1. Graph Construction:

g = [[] for _ in range(n)]
for a, b in connections:
    g[a].append((b, 1))  # Original edge: a→b needs reversal (cost=1)
    g[b].append((a, 0))  # Reverse edge: b→a doesn't need reversal (cost=0)

We build an adjacency list g where each city has a list of (neighbor, cost) tuples:

• For each original directed edge [a, b], we add it to the graph twice
• g[a].append((b, 1)): If we traverse from a to b, we're going against the original direction (away from city 0), so we need to reverse this edge (cost=1)
• g[b].append((a, 0)): If we traverse from b to a, we're following the reverse of the original direction (toward city 0), so no reversal needed (cost=0)

2. DFS Traversal:

def dfs(a: int, fa: int) -> int:
    return sum(c + dfs(b, a) for b, c in g[a] if b != fa)

The DFS function takes two parameters:

• a: Current city we're visiting
• fa: Parent city (where we came from) to avoid revisiting

The function recursively:

• Iterates through all neighbors (b, c) of current city a
• Skips the parent city fa to avoid going backward in the tree
• For each unvisited neighbor b, adds the edge cost c (0 or 1) to the result
• Recursively calls DFS on neighbor b with a as its parent
• Returns the sum of all reversal costs in the subtree rooted at a

3. Starting the DFS:

return dfs(0, -1)

We start DFS from city 0 with parent -1 (indicating no parent for the root). The function returns the total number of edges that need to be reversed.

Time Complexity: O(n) - We visit each city once and process each edge twice (once from each direction).

Space Complexity: O(n) - For the adjacency list and recursion stack depth (which can be up to n in a skewed tree).

The elegance of this solution lies in encoding the reversal information directly into the graph structure, allowing a simple DFS traversal to calculate the answer by just summing up edge costs.

Example Walkthrough

Let's walk through a small example with 4 cities and the following connections:

• connections = [[0,1], [0,2], [3,2]]

This creates a tree where:

• City 0 connects to city 1 (road: 0→1)
• City 0 connects to city 2 (road: 0→2)
• City 3 connects to city 2 (road: 3→2)

Step 1: Build the Graph

For each directed edge, we add two entries to our adjacency list:

• For edge [0,1]: Add (1, cost=1) to g[0] and (0, cost=0) to g[1]
• For edge [0,2]: Add (2, cost=1) to g[0] and (0, cost=0) to g[2]
• For edge [3,2]: Add (2, cost=1) to g[3] and (3, cost=0) to g[2]

Our adjacency list becomes:

g[0] = [(1, 1), (2, 1)]  // From 0, we can go to 1 and 2 (both need reversal)
g[1] = [(0, 0)]          // From 1, we can go to 0 (no reversal needed)
g[2] = [(0, 0), (3, 0)]  // From 2, we can go to 0 and 3 (neither needs reversal)
g[3] = [(2, 1)]          // From 3, we can go to 2 (needs reversal)

Step 2: DFS Traversal from City 0

Starting dfs(0, -1):

• Current city: 0, parent: -1
• Neighbors: [(1, 1), (2, 1)]
• Process neighbor 1:
  • Cost = 1 (edge 0→1 needs reversal)
  • Call dfs(1, 0):
    • Current city: 1, parent: 0
    • Neighbors: [(0, 0)]
    • Skip 0 (it's the parent)
    • Return 0
  • Subtotal from branch 1: 1 + 0 = 1
• Process neighbor 2:
  • Cost = 1 (edge 0→2 needs reversal)
  • Call dfs(2, 0):
    • Current city: 2, parent: 0
    • Neighbors: [(0, 0), (3, 0)]
    • Skip 0 (it's the parent)
    • Process neighbor 3:
      • Cost = 0 (edge 3→2 doesn't need reversal when traversing 2→3)
      • Call dfs(3, 2):
        • Current city: 3, parent: 2
        • Neighbors: [(2, 1)]
        • Skip 2 (it's the parent)
        • Return 0
      • Subtotal from branch 3: 0 + 0 = 0
    • Return 0
  • Subtotal from branch 2: 1 + 0 = 1
• Total: 1 + 1 = 2

Result: 2 roads need to be reversed (0→1 becomes 1→0, and 0→2 becomes 2→0)

This matches our intuition: cities 1 and 2 cannot reach city 0 because the roads point away from it. After reversing these two roads, all cities can reach the capital.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm builds an adjacency list representation of the graph and then performs a depth-first search (DFS) starting from node 0.

• Building the graph takes O(n-1) time since there are n-1 connections (edges) in a tree with n nodes. For each connection, we add two entries to the adjacency list in constant time.
• The DFS visits each node exactly once. At each node, we iterate through its neighbors. Since this is a tree structure with n nodes and n-1 edges, each edge is traversed exactly twice (once from each direction). The total work done across all nodes is O(n + 2(n-1)) = O(n).

Space Complexity: O(n)

The space usage consists of:

• The adjacency list g which stores 2(n-1) entries total across all nodes, requiring O(n) space.
• The recursive call stack for DFS, which in the worst case (a linear tree) can go up to depth n, requiring O(n) space.
• The function parameters and local variables use constant space per call.

Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Direction Logic

A common mistake is getting confused about when an edge needs to be reversed. Many people incorrectly think:

• "If we traverse from a to b in DFS, we need to reverse the edge"

The Correct Logic:

• When DFS traverses from city a to city b, we're exploring outward from city 0
• If the original edge was a→b, then this edge points AWAY from city 0, so it needs reversing (cost=1)
• If the original edge was b→a, then this edge already points TOWARD city 0, so no reversal needed (cost=0)

Wrong Implementation:

# INCORRECT: Confusing the reversal logic
for from_city, to_city in connections:
    adjacency_list[from_city].append((to_city, 0))  # Wrong!
    adjacency_list[to_city].append((from_city, 1))  # Wrong!

Correct Implementation:

for from_city, to_city in connections:
    adjacency_list[from_city].append((to_city, 1))  # Correct: traversing along original direction needs reversal
    adjacency_list[to_city].append((from_city, 0))  # Correct: traversing against original direction doesn't need reversal

2. Forgetting to Track Visited Nodes

Without tracking the parent/visited nodes, the DFS will infinite loop:

Wrong Implementation:

def count_reversals(current_city: int) -> int:
    total = 0
    for neighbor, cost in adjacency_list[current_city]:
        # This will revisit the parent and cause infinite recursion!
        total += cost + count_reversals(neighbor)
    return total

Correct Implementation:

def count_reversals(current_city: int, parent_city: int) -> int:
    total = 0
    for neighbor, cost in adjacency_list[current_city]:
        if neighbor != parent_city:  # Skip parent to avoid cycles
            total += cost + count_reversals(neighbor, current_city)
    return total

3. Building Only Unidirectional Graph

Some might try to build the graph with only the original edges:

Wrong Implementation:

# Only adding original edges - DFS can't traverse the full tree!
for from_city, to_city in connections:
    adjacency_list[from_city].append(to_city)

This fails because DFS starting from city 0 can't reach cities that have edges pointing toward it. The bidirectional representation is essential for complete traversal.

4. Using Wrong Data Structure

Using a dictionary with single values instead of lists for multiple neighbors:

Wrong Implementation:

# This overwrites previous neighbors!
adjacency_list = {}
for from_city, to_city in connections:
    adjacency_list[from_city] = (to_city, 1)  # Overwrites previous neighbor
    adjacency_list[to_city] = (from_city, 0)  # Overwrites previous neighbor

Correct Implementation:

adjacency_list = [[] for _ in range(n)]
for from_city, to_city in connections:
    adjacency_list[from_city].append((to_city, 1))
    adjacency_list[to_city].append((from_city, 0))