Find minimum reversals to orient edges away from root

You are given a connected graph with n nodes labeled 0..n-1 and n-1 directed edges. If you ignore edge directions, the edges form a tree.

Each directed edge is given as a pair (u, v) meaning the edge currently points from u to v.

You are also given a root node r.

In the rooted tree (rooted at r), every edge should point away from the root (i.e., from parent to child). You may reverse the direction of any edge; each reversal costs 1.

Return the minimum total number of edge reversals required so that, after reversals, all edges in the tree point away from r.

Input

• Integer n
• List of directed edges edges, length n-1, each as (u, v)
• Integer root r

Output

• Integer: minimum number of reversals

Example

Suppose n = 5, r = 0, and edges are:

• (1, 0), (0, 2), (3, 2), (3, 4)

Ignoring directions, the tree is 0-1, 0-2, 2-3, 3-4. To make all edges point away from 0, edges (1,0) and (3,2) must be reversed, so the answer is 2.

Constraints (typical)

• 1 <= n <= 2e5
• The undirected version of edges is a tree
• Nodes are 0..n-1

Note: With large n, recursive DFS may overflow the call stack in some languages; an iterative traversal may be required.

Find minimum reversals to orient edges away from root

Hints

1. Rooting the tree at r forces a unique target direction for every edge: parent -> child. There is no choice to optimize across edges, so the answer is just the count of edges whose current direction disagrees.
2. Build an undirected adjacency list so you can walk the tree in any direction, but tag each entry with a cost: for original edge (u, v), add (v, 0) to adj[u] (forward = free) and (u, 1) to adj[v] (backward = one reversal).
3. Traverse outward from r with BFS or an explicit stack and sum the cost tag of each edge crossed in the parent -> child direction. Use an iterative traversal — a recursive DFS can overflow the stack on a 2e5-deep path.

Solution

Intuition

Strip away the edge directions and you have a plain tree. Rooting that tree at r fixes a unique parent → child relationship for every edge: in the final orientation each edge must point from the parent toward the child.

So for every edge we already know what its target direction is once we root at r. The only question for each edge is: does its current direction already match the target, or do we have to pay 1 to reverse it?

That makes the whole problem a single traversal from r:

• Walk the tree starting at the root.
• When we move from a node parent to an unvisited neighbor child, that tree edge must end up oriented parent → child.
• If the original edge was stored as (parent, child) it is already correct → cost 0.
• If the original edge was stored as (child, parent) it points toward the root along this branch → it must be reversed → cost 1.

Sum the costs. There is no optimization or choice to make — each edge's required direction is forced by the rooting, so the minimum is simply the count of edges that disagree. A greedy "reverse exactly the wrong ones" is optimal because the orientations of different tree edges are independent.

Key modeling trick: tag direction in the adjacency list

We need to know, while traversing, whether an edge was originally u → v or v → u. Build an undirected adjacency list (so we can walk the tree in any direction), but tag each entry with a cost:

• For an original edge (u, v):
  • Add (v, cost = 0) to adj[u] — traversing u → v follows the original direction, free.
  • Add (u, cost = 1) to adj[v] — traversing v → u goes against the original direction, costs a reversal.

Now a traversal outward from the root simply accumulates the cost tag of each edge it crosses in the parent → child direction.

Algorithm

1. Build the tagged undirected adjacency list as above.
2. Traverse from r (BFS or iterative DFS), marking nodes visited.
3. For each newly discovered child edge, add its tag (0 or 1) to the answer.
4. Return the accumulated cost.

Why iterative (not recursive)

With n up to 2 \times 10^5, the tree can be a single path of depth ~2 \times 10^5. A recursive DFS would recurse that deep and blow the call stack (Python's default limit is ~1000; many languages crash similarly). Use an explicit stack or a queue. BFS is the cleanest choice here and avoids the recursion entirely.

Reference solution (Python — iterative BFS)

from collections import deque

def min_reversals(n, edges, r):
    # adj[node] = list of (neighbor, cost_to_orient_node->neighbor)
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append((v, 0))  # u -> v already correct
        adj[v].append((u, 1))  # v -> u must be reversed

    visited = [False] * n
    visited[r] = True
    q = deque([r])
    cost = 0

    while q:
        node = q.popleft()
        for nei, c in adj[node]:
            if not visited[nei]:
                visited[nei] = True
                cost += c          # orienting node -> nei costs c
                q.append(nei)
    return cost

Iterative DFS variant

Identical logic with a stack, if DFS order is preferred:

def min_reversals_dfs(n, edges, r):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append((v, 0))
        adj[v].append((u, 1))

    visited = [False] * n
    visited[r] = True
    stack = [r]
    cost = 0

    while stack:
        node = stack.pop()
        for nei, c in adj[node]:
            if not visited[nei]:
                visited[nei] = True
                cost += c
                stack.append(nei)
    return cost

Trace on the example

n = 5, r = 0, edges (1,0), (0,2), (3,2), (3,4).

Tagged adjacency. For an edge (u, v), the source endpoint u gets the free entry (v, 0) and the target endpoint v gets the reversal entry (u, 1):

Edge (u,v)	Entry added at source u	Entry added at target v
(1,0)	adj[1] += (0,0)	adj[0] += (1,1)
(0,2)	adj[0] += (2,0)	adj[2] += (0,1)
(3,2)	adj[3] += (2,0)	adj[2] += (3,1)
(3,4)	adj[3] += (4,0)	adj[4] += (3,1)

BFS from 0:

• 0 → 1 via adj[0]'s (1, 1) → cost +1 (edge was (1,0), reversed). Running total 1.
• 0 → 2 via (2, 0) → cost +0 (edge was (0,2), already correct). Total 1.
• From 2: neighbor 0 visited; 2 → 3 via (3, 1) → cost +1 (edge was (3,2), reversed). Total 2.
• From 3: neighbor 2 visited; 3 → 4 via (4, 0) → cost +0 (edge was (3,4), already correct). Total 2.

Answer: 2, matching the expected output. The two reversed edges are exactly (1,0) and (3,2).

Complexity

• Time: $O(n)$ — building the adjacency list touches each of the n-1 edges once; the traversal visits each node once and each edge twice (once from each endpoint).
• Space: $O(n)$ — adjacency list, visited array, and the BFS queue / DFS stack are all linear in n.

This is optimal: any correct algorithm must at least read all n-1 edges.

Edge cases

• n = 1: no edges, the loop never runs, answer is 0. The single root node is trivially valid.
• Root with no incoming/outgoing issue: handled uniformly — every edge is classified purely by the rooting, so the choice of r is the only thing that matters.
• Edges given in either orientation: the (v, 1) reverse-tag entry makes the traversal direction-agnostic for walking but direction-aware for costing, so input order of u, v within an edge doesn't break anything.
• Deep path / star shapes: the iterative traversal handles a 2 \times 10^5-deep path without stack overflow; a star (one center, many leaves) is fine since the queue/stack holds at most O(n) nodes.
• Self-consistency check: because the undirected graph is guaranteed to be a tree (connected, n-1 edges), the traversal from r reaches every node exactly once — no need to handle cycles or disconnected components.

Common pitfalls

• Recursive DFS on large inputs — the single most likely failure here; the problem statement explicitly warns about it. Always go iterative for n up to 2 \times 10^5.
• Forgetting the tree is undirected for traversal. If you only follow original edge directions, you can't even reach all nodes from r. You must walk both ways and charge for the wrong direction, rather than only following arrows.
• Double counting. Mark a node visited when you enqueue/discover it (as above) so each edge contributes its cost exactly once.
• Over-thinking it. There's no DP or min-cut here. Each edge's required orientation is forced; the answer is just the count of mismatches. Resist the urge to "optimize across edges."