Minimum Edge Inversions - Arista Online Assessment

Problem Preview

"Optimize a directed graph representing a neural network by selecting a root node that minimizes the number of edge reversals needed. The graph has `n` nodes numbered from `1` to `n` and `n - 1` edges, where the `i`th edge connects node `g_from[i]` to node `g_to[i]`. Select any node as the root, then reverse as many edges as necessary to make **all edges flow away from the root**. Find the root node choice that requires the minimum number of edge reversals. ### Example ```text g_nodes = 4 g_from = [1, 2, 3] g_to = [4, 4, 4] ``` The graph is: ```text 2 → 4 ←1 ↑ 3 ``` If node `2` is selected as the root, edges `1 → 4` and `3 → 4` need to be reversed. After reversal: ```text 2 ↓ 4 ↙ ↘ 3 1 ``` Hence, the minimum number of edges to be inverted is **2**.  ### Returns `int`: the minimum number of edges that must be inverted. ### Constraints * `2 ≤ g_nodes ≤ 10^5` * `1 ≤ g_from[i], g_to[i] ≤ g_nodes` * `g_from[i] ≠ g_to[i]` "