FastPrepFastPrep
Problem Brief

Minimum Edge Reversals to Root a Tree

FULLTIMEOA

You are given a directed version of a tree with n nodes labeled from 0 to n - 1. Each undirected edge of the tree appears once in the input as a directed edge u -> v.

You may choose any node as the root. After choosing the root, every edge should point away from that root. You may reverse edges, and each reversed edge costs 1.

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

Function Description

Complete the function minEdgeReversalsForRoot in the editor below.

minEdgeReversalsForRoot has the following parameters:

  1. int n: the number of nodes
  2. int[][] edges: directed edges where edges[i] = [u, v] means the current direction is u -> v

Returns

int: the minimum number of reversals required.

1Example 1

Input
n = 5, edges = [[0, 1], [2, 1], [3, 2], [3, 4]]
Output
1
Explanation

If node 3 is chosen as the root, the desired directions are 3 -> 2 -> 1 -> 0 and 3 -> 4. Only the edge 0 -> 1 must be reversed.

2Example 2

Input
n = 4, edges = [[2, 0], [0, 1], [2, 3]]
Output
0
Explanation

Choosing node 2 as the root already makes every edge point away from the root, so no reversals are needed.

Constraints

Limits and guarantees your solution can rely on.

The source thread did not provide explicit numeric bounds.

  • The underlying undirected graph formed by edges is a tree.
  • edges.length = n - 1.
  • Each input edge gives the current direction of exactly one tree edge.
public int minEdgeReversalsForRoot(int n, int[][] edges) {
    // write your code here
}
Input

n

5

edges

[[0, 1], [2, 1], [3, 2], [3, 4]]

Output

1

Sign in to submit your solution.