0986MediumDepth-First SearchBreadth-First SearchGraph Theory

Roads to Turn Round for the Depot

Tracked in this browser only

Trains the technique from

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

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A region has n towns numbered from zero, joined by n - 1 one-way roads listed in connections, each [from, to]. Ignoring the directions, the roads join every town to every other with no loops.

Return the fewest roads that must be turned round so that every town can reach town 0 by following the roads the way they point.

Examples

Example 1

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

Sweeping outwards from town 0, the roads to 1, to 3 and to 5 all point away from it and must be turned; the roads from 2 and from 4 already point the right way.

Example 2

Input: n = 4, connections = [[3, 2], [2, 1], [1, 0]]
Output: 0

The towns run in a line and every road already points towards town 0.

Example 3

Input: n = 4, connections = [[0, 1], [1, 2], [2, 3]]
Output: 3

The towns run in a line and every road points away from town 0, so all three must be turned.

Constraints

2 <= n <= 5 * 10^4
connections.length == n - 1
connections[i].length == 2
0 <= connections[i][0] <= n - 1
0 <= connections[i][1] <= n - 1
The two towns on a road are different
Ignoring directions, the roads join every town with no loops

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def min_reorder(n: int, connections: list[list[int]]) -> int:

Java

public int minReorder(int n, int[][] connections)

The intended approach

Time O(n) for n towns: one sweep over the tree.Space O(n) for the road lists.

Ignoring directions the roads form a tree, so between any town and town `0` there is exactly one route, and every road on that route must point towards `0`. Since each road lies on the route of everything beyond it, the condition comes down to something local: walking outwards from town `0`, a road must point back the way we came. So sweep outwards from town `0` over the roads with their directions ignored, and count the roads met pointing away from `0` rather than towards it. Recording each road's direction when the roads are read in makes that one test per road, and each road is met exactly once.

Pythonentry point: min_reorder

def min_reorder(n, connections):
    from collections import deque
    adj = [[] for _ in range(n)]
    for a, b in connections:
        adj[a].append((b, True))     # pointing away from a
        adj[b].append((a, False))    # pointing towards b
    seen = [False] * n
    seen[0] = True
    queue = deque([0])
    turned = 0
    while queue:
        town = queue.popleft()
        for nxt, outward in adj[town]:
            if seen[nxt]:
                continue
            seen[nxt] = True
            if outward:
                turned += 1
            queue.append(nxt)
    return turned

The obvious version

For each town, walk its route to town `0` step by step, checking each road along the way and noting the ones pointing the wrong way, then count the distinct roads noted. Costs a route per town and sweeps nothing outwards.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_min_reorder(n, connections):
    from collections import deque
    adj = [[] for _ in range(n)]
    for at in range(len(connections)):
        a, b = connections[at]
        adj[a].append((b, at))
        adj[b].append((a, at))
    wrong = set()
    for start in range(1, n):
        # find the route from this town to town 0
        came = {start: None}
        queue = deque([start])
        while queue:
            town = queue.popleft()
            if town == 0:
                break
            for nxt, road in adj[town]:
                if nxt not in came:
                    came[nxt] = (town, road)
                    queue.append(nxt)
        at = 0
        route = []
        while came[at] is not None:
            prev, road = came[at]
            route.append((prev, at, road))
            at = prev
        for prev, here, road in route:
            a, b = connections[road]
            # travelling towards town 0 goes from prev to here, so the road is
            # already right when it points that way
            if a == prev and b == here:
                continue
            wrong.add(road)
    return len(wrong)

How this problem was checked

Reference solution executed against 10 test cases — 10 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in