LeetCode 1466 - Reorder Routes to Make All Paths Lead to the City Zero

The problem gives us a directed graph of cities connected by roads. There are n cities numbered from 0 to n - 1, and exactly n - 1 roads. Since the graph contains n - 1 edges and there is exactly one path between any pair of cities, the graph forms a tree.

leetcodemediumdepth-first-searchbreadth-first-searchgraph-theory

LeetCode Problem 1466

Difficulty: 🟡 Medium
Topics: Depth-First Search, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem gives us a directed graph of cities connected by roads. There are n cities numbered from 0 to n - 1, and exactly n - 1 roads. Since the graph contains n - 1 edges and there is exactly one path between any pair of cities, the graph forms a tree.

Each road currently has a direction. A connection [a, b] means the road is directed from city a to city b.

The goal is to make sure every city can reach city 0 by following the directions of the roads. We are allowed to reverse the direction of roads, and we want to find the minimum number of reversals needed.

Another way to think about the problem is this: after all changes are made, every path in the tree must ultimately lead toward city 0.

The input consists of:

  • n, the number of cities
  • connections, a list of directed roads

The output is a single integer representing the minimum number of roads whose direction must be changed.

The constraints are important because they determine what type of solution is feasible.

The number of cities can be as large as 5 * 10^4, which means we need a solution close to linear time. Any approach that repeatedly traverses the graph or tries many combinations of edge reversals would be too slow.

The graph is guaranteed to be a tree, which gives us several useful properties:

  • There are no cycles
  • There is exactly one path between any two cities
  • Every edge is essential for connectivity

These guarantees simplify the problem significantly because we never need to worry about multiple alternative routes.

Several edge cases are important:

  • Some roads may already point toward city 0, requiring no changes
  • All roads may point away from city 0, requiring many reversals
  • The tree may be highly unbalanced, resembling a linked list
  • The graph may already satisfy the condition, producing an answer of 0

The problem also guarantees that it is always possible to reorder roads so every city can reach city 0.

Approaches

Brute Force Approach

A brute-force solution would try different combinations of edge reversals and then check whether every city can reach city 0.

One possible implementation would iterate through subsets of edges, reverse those edges, and run a reachability check using BFS or DFS from every node. If all nodes can reach city 0, the subset is valid. The smallest valid subset would be the answer.

This approach is correct because it eventually examines every possible set of reversals. However, it is computationally infeasible.

A tree with n - 1 edges has 2^(n-1) possible reversal combinations. For each combination, we may need graph traversals to verify connectivity. With n up to 50000, this approach is completely impractical.

Optimal Approach

The key insight comes from understanding the structure of the tree.

Since the graph is a tree, there is exactly one path from every node to city 0. Therefore, for every edge, there is only one correct direction if we want all paths to lead to 0.

We can treat the graph as undirected for traversal purposes while remembering the original edge directions.

Starting from city 0, we perform DFS or BFS through the tree.

Whenever we traverse an edge:

  • If the edge originally points away from city 0, it must be reversed
  • If the edge already points toward city 0, it is correct

The traversal naturally visits every edge exactly once, and each incorrectly directed edge contributes exactly one reversal to the answer.

This works because in a tree, every node has a unique parent relationship relative to city 0.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Tries all reversal combinations
Optimal O(n) O(n) DFS/BFS traversal counting incorrect directions

Algorithm Walkthrough

  1. Build an adjacency list representation of the graph.

Since we need to traverse the tree in both directions, we create an undirected representation. However, we also need to remember whether each edge was originally directed away from the current node.

For every directed edge [a, b]:

  • Add (b, 1) to a's adjacency list because traveling from a to b follows the original direction, meaning this edge would need reversal if we are moving away from city 0
  • Add (a, 0) to b's adjacency list because traveling from b to a goes against the original direction, meaning the edge already points correctly toward city 0
  1. Start DFS or BFS from city 0.

City 0 is the destination for all paths, so it becomes the root of our traversal. 3. Maintain a visited set or parent tracking.

Since the graph is undirected in our traversal structure, we must avoid revisiting nodes and creating infinite loops. 4. Traverse each neighboring city.

For every adjacent node:

  • If the edge cost is 1, the road currently points away from city 0, so increment the answer
  • Continue traversal recursively or iteratively
  1. Continue until all nodes are visited.

Since the graph is connected and contains n - 1 edges, traversing from city 0 reaches every node exactly once. 6. Return the total number of reversals counted.

Why it works

The algorithm works because every node in a tree has exactly one path to city 0. During traversal, if an edge points away from the root direction, that edge prevents nodes in its subtree from reaching city 0. Reversing it is necessary and sufficient.

Since each edge is examined exactly once, and every incorrectly oriented edge is counted exactly once, the final count is the minimum number of reversals required.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        graph = defaultdict(list)

        for a, b in connections:
            graph[a].append((b, 1))
            graph[b].append((a, 0))

        visited = set()

        def dfs(city: int) -> int:
            visited.add(city)

            changes = 0

            for neighbor, needs_reversal in graph[city]:
                if neighbor not in visited:
                    changes += needs_reversal
                    changes += dfs(neighbor)

            return changes

        return dfs(0)

The implementation begins by constructing an adjacency list. Each entry stores both the neighboring node and a flag indicating whether traversing that edge follows the original direction.

For an original edge a -> b:

  • Moving from a to b means the edge points away from city 0, so it may require reversal
  • Moving from b to a means the edge already points toward city 0

The DFS traversal starts at city 0. A visited set prevents revisiting nodes because the traversal graph is undirected.

Inside DFS, every unvisited neighbor is explored. If the edge direction is incorrect relative to the traversal toward city 0, the algorithm increments the reversal counter.

The recursive calls accumulate the total number of reversals across the entire tree.

Go Solution

package main

func minReorder(n int, connections [][]int) int {
	graph := make([][][2]int, n)

	for _, edge := range connections {
		a, b := edge[0], edge[1]

		graph[a] = append(graph[a], [2]int{b, 1})
		graph[b] = append(graph[b], [2]int{a, 0})
	}

	visited := make([]bool, n)

	var dfs func(int) int

	dfs = func(city int) int {
		visited[city] = true

		changes := 0

		for _, neighbor := range graph[city] {
			nextCity := neighbor[0]
			needsReversal := neighbor[1]

			if !visited[nextCity] {
				changes += needsReversal
				changes += dfs(nextCity)
			}
		}

		return changes
	}

	return dfs(0)
}

The Go implementation follows the same logic as the Python solution.

Instead of Python tuples, Go uses fixed-size arrays [2]int to store neighbor information.

A boolean slice is used instead of a set for tracking visited nodes because city labels range from 0 to n - 1, making indexed lookup efficient.

The DFS function is implemented as a closure so it can access the graph and visited slice directly.

Since the maximum answer is at most n - 1, integer overflow is not a concern with Go's standard int type.

Worked Examples

Example 1

Input:

n = 6
connections = [[0,1],[1,3],[2,3],[4,0],[4,5]]

Constructed graph:

City Neighbors
0 (1,1), (4,0)
1 (0,0), (3,1)
2 (3,1)
3 (1,0), (2,0)
4 (0,1), (5,1)
5 (4,0)

DFS traversal:

Current City Neighbor Needs Reversal Total Changes
0 1 Yes 1
1 3 Yes 2
3 2 No 2
0 4 No 2
4 5 Yes 3

Final answer:

3

Example 2

Input:

n = 5
connections = [[1,0],[1,2],[3,2],[3,4]]

DFS traversal:

Current City Neighbor Needs Reversal Total Changes
0 1 No 0
1 2 Yes 1
2 3 No 1
3 4 Yes 2

Final answer:

2

Example 3

Input:

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

DFS traversal:

Current City Neighbor Needs Reversal Total Changes
0 1 No 0
0 2 No 0

Final answer:

0

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node and edge is visited once
Space O(n) Adjacency list and visited structure

The graph contains exactly n - 1 edges because it is a tree. Building the adjacency list takes linear time.

The DFS traversal visits every node once and examines every edge once. Since each edge contributes constant work, the total runtime is linear.

The adjacency list stores both directions of every edge, requiring O(n) space. The visited set and recursion stack also require linear space in the worst case.

Test Cases

from typing import List

class Solution:
    def minReorder(self, n: int, connections: List[List[int]]) -> int:
        from collections import defaultdict

        graph = defaultdict(list)

        for a, b in connections:
            graph[a].append((b, 1))
            graph[b].append((a, 0))

        visited = set()

        def dfs(city):
            visited.add(city)

            changes = 0

            for neighbor, needs_reversal in graph[city]:
                if neighbor not in visited:
                    changes += needs_reversal
                    changes += dfs(neighbor)

            return changes

        return dfs(0)

solution = Solution()

assert solution.minReorder(
    6,
    [[0,1],[1,3],[2,3],[4,0],[4,5]]
) == 3  # Example 1

assert solution.minReorder(
    5,
    [[1,0],[1,2],[3,2],[3,4]]
) == 2  # Example 2

assert solution.minReorder(
    3,
    [[1,0],[2,0]]
) == 0  # Example 3

assert solution.minReorder(
    2,
    [[0,1]]
) == 1  # Smallest tree requiring reversal

assert solution.minReorder(
    2,
    [[1,0]]
) == 0  # Smallest tree already correct

assert solution.minReorder(
    4,
    [[0,1],[1,2],[2,3]]
) == 3  # All edges point away from city 0

assert solution.minReorder(
    4,
    [[1,0],[2,1],[3,2]]
) == 0  # All edges already point toward city 0

assert solution.minReorder(
    5,
    [[1,0],[2,0],[3,0],[4,0]]
) == 0  # Star graph already correct

assert solution.minReorder(
    5,
    [[0,1],[0,2],[0,3],[0,4]]
) == 4  # Star graph fully incorrect
Test Why
Example 1 Validates mixed edge directions
Example 2 Tests deeper tree traversal
Example 3 Verifies zero reversals
Two-node incorrect tree Smallest non-trivial case
Two-node correct tree Minimal valid input
Linear chain away from 0 Worst-case reversals
Linear chain toward 0 No reversals needed
Correct star graph Multiple incoming edges
Incorrect star graph Multiple outgoing edges

Edge Cases

One important edge case occurs when all roads already point toward city 0. In this scenario, the correct answer is 0. A buggy implementation might incorrectly count edges simply because they are traversed during DFS. This implementation avoids that issue by explicitly storing whether an edge needs reversal and only incrementing the answer when necessary.

Another critical edge case is a completely incorrect chain such as 0 -> 1 -> 2 -> 3. Every edge must be reversed. Recursive traversal correctly identifies each outward-facing edge because every DFS step moving away from city 0 follows the original direction.

A highly unbalanced tree can also be problematic because recursive DFS may become deep. The algorithm still works correctly because each node is visited exactly once. In Python, recursion depth could theoretically become an issue for extremely deep trees, although the problem constraints are typically manageable in LeetCode's environment. An iterative DFS or BFS could be used if recursion limits were a concern.

A star-shaped graph centered at city 0 is another useful edge case. If all edges point outward from 0, every edge must be reversed. If all edges point inward, none should be reversed. The adjacency encoding cleanly handles both cases because each edge independently records whether it is correctly oriented relative to traversal from city 0.