Choose root to minimize edge reversals

Q: Choose root to minimize edge reversals

This question evaluates understanding of directed versus undirected graph representations, tree rooting, and optimization of edge orientations, testing competency in graph algorithms and tree re-rooting reasoning.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Problem

You are given a connected graph with n nodes labeled 0..n-1 and n-1 directed edges. If you ignore directions, the edges form a tree (i.e., the underlying undirected graph is a tree).

You may pick any node r as the root. You are allowed to reverse the direction of any edge; reversing one edge costs 1.

Your goal is to choose a root r and reverse as few edges as possible so that, in the final directed tree, every edge points away from the root (equivalently: for every node v != r, the unique path from r to v follows edge directions from parent to child).

Input

Integer n
List of directed edges edges , where each edge is a pair (u, v) meaning a directed edge u -> v

Output

Return the minimum number of edge reversals needed over all choices of root r.

Constraints (typical)

1 <= n <= 2 * 10^5
len(edges) = n - 1
The underlying undirected graph is connected (a tree)

Example

If n = 3 and edges = [(0,1), (2,0)]:

Choosing root 0 requires reversing (2,0) to (0,2) → cost 1
Choosing root 2 requires reversing (0,1) and (2,0) ? (check orientation away from 2) → higher So the answer is 1 .