DeepSeek LeetCode 2858. 可以到达每一个节点的最少边反转次数 Java实现

问题分析这道题的关键在于给定一个有向树如果忽略方向就是一棵树对每个节点 i计算最少需要反转多少条边使得从 i 出发能到达所有节点。核心思路是换根DPRerooting DP1. 先任选一个根比如节点 0计算从它出发需要的反转次数2. 当根从父节点移动到子节点时只有它们之间的那条边方向会发生变化其他边的状态不变算法思路建图技巧将每条边存储为双向的并带上权重标记原始方向· 正向边 u → v 存储为 (v, 1) 表示从 u 到 v 方向与原边一致· 反向边 v → u 存储为 (u, -1) 表示与原边方向相反这样在换根时ans[child] ans[parent] k 其中 k 就是这条边的权重恰好对应 ±1 的调整。Java实现javaclass Solution {// 邻接表每个元素是 [邻居节点, 权重]// 权重 1 表示从当前节点到邻居是原边方向// 权重 -1 表示从当前节点到邻居是原边的反方向private Listint[][] g;private int[] ans;private int n;public int[] minEdgeReversals(int n, int[][] edges) {this.n n;g new List[n];for (int i 0; i n; i) {g[i] new ArrayList();}// 建图每条边存储两个方向用权重标识方向for (int[] e : edges) {int u e[0], v e[1];// 原边方向u - v权重1表示不需要反转即可从u走向vg[u].add(new int[]{v, 1});// 反向边v - u权重-1表示需要反转才能从v走向ug[v].add(new int[]{u, -1});}ans new int[n];// 第一次DFS计算从节点0出发需要的反转次数// 反转次数 所有权重为-1的边的数量因为这些边需要反转才能从0出发到达ans[0] dfs1(0, -1);// 第二次DFS换根DP计算所有节点的答案dfs2(0, -1);return ans;}// 第一次DFS以0为根计算需要反转的边数private int dfs1(int u, int parent) {int res 0;for (int[] edge : g[u]) {int v edge[0];int w edge[1];if (v parent) continue;// 如果权重是-1说明这条边在原图中是从v指向u// 从u出发需要反转这条边所以计数1res (w -1 ? 1 : 0);res dfs1(v, u);}return res;}// 第二次DFS换根DP// 当根从u换到v时ans[v] ans[u] k// 其中k是边(u,v)的权重// 如果k1说明原边u-v从v出发需要多反转一次才能到达u// 如果k-1说明原边v-u从v出发少反转一次private void dfs2(int u, int parent) {for (int[] edge : g[u]) {int v edge[0];int w edge[1];if (v parent) continue;// 关键转移公式ans[v] ans[u] w;dfs2(v, u);}}}代码详解部分 说明g[u].add(new int[]{v, 1}) 存储原边方向 u→v权重1g[v].add(new int[]{u, -1}) 存储反向边 v→u权重-1dfs1 中的 w -1 ? 1 : 0 统计从0出发需要反转的边那些指向父节点的边dfs2 中的 ans[v] ans[u] w 换根DP核心公式通过权重±1快速调整复杂度分析· 时间复杂度O(n)每个节点和每条边只遍历两次· 空间复杂度O(n)邻接表存储 递归栈空间示例验证以输入 n 4, edges [[2,0],[2,1],[1,3]] 为例· 节点2出发不需要反转 → ans[2]0· 节点0出发需要反转 2→0 → ans[0]1· 节点1出发需要反转 2→1 → ans[1]1· 节点3出发需要反转 1→3 和 2→1 → ans[3]2输出 [1,1,0,2]与题目示例一致。