Minimum Reversal

Problem Statement

Minimum Reversal Problem Description 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 m edges, where the i th edge connects node g_from[i] to g_to[i] . It is guaranteed that the underlying undirected graph is a tree. Select any node as the root, then reverse as many edges as necessary to make all edges flow away from the root (i.e., for every node, there is a unique directed path from the root to that node). Find the root node choice that requires the minimum number of edge reversals. Example Given g_nodes = 4 and the edges are 1 → 4 , 2 → 4 , 3 → 4 . g_nodes = 4 g_from = [1, 2, 3] g_to = [4, 4, 4] The initial graph looks like this, with all nodes pointing to node 4: If we select node 2 as the root, we want to have directed paths from node 2 to all other nodes (1, 3, 4). The edge 2 → 4 is already oriented correctly. To reach node 1, we need a path from 2. W