Go 实现gofunc minEdgeReversals(n int, edges [][]int) []int {// 邻接表每个元素是 [邻居节点, 权重]// 权重 1 表示从当前节点到邻居是原边方向// 权重 -1 表示从当前节点到邻居是原边的反方向g : make([][][2]int, n)for i : 0; i n; i {g[i] make([][2]int, 0)}// 建图每条边存储两个方向用权重标识方向for _, e : range edges {u, v : e[0], e[1]// 原边方向u - v权重1表示不需要反转即可从u走向vg[u] append(g[u], [2]int{v, 1})// 反向边v - u权重-1表示需要反转才能从v走向ug[v] append(g[v], [2]int{u, -1})}ans : make([]int, n)// 第一次DFS计算从节点0出发需要的反转次数// 反转次数 所有权重为-1的边的数量var dfs1 func(int, int) intdfs1 func(u, parent int) int {res : 0for _, edge : range g[u] {v, w : edge[0], edge[1]if v parent {continue}// 如果权重是-1说明这条边在原图中是从v指向u// 从u出发需要反转这条边所以计数1if w -1 {res}res dfs1(v, u)}return res}ans[0] dfs1(0, -1)// 第二次DFS换根DP// 当根从u换到v时ans[v] ans[u] k// 其中k是边(u,v)的权重// 如果k1说明原边u-v从v出发需要多反转一次才能到达u// 如果k-1说明原边v-u从v出发少反转一次var dfs2 func(int, int)dfs2 func(u, parent int) {for _, edge : range g[u] {v, w : edge[0], edge[1]if v parent {continue}// 关键转移公式ans[v] ans[u] wdfs2(v, u)}}dfs2(0, -1)return ans}代码结构说明部分 说明g[u] append(g[u], [2]int{v, 1}) 存储原边方向 u→v权重1g[v] append(g[v], [2]int{u, -1}) 存储反向边 v→u权重-1w -1 判断是否需要反转该边ans[0] dfs1(0, -1) 以0为根计算初始反转次数ans[v] ans[u] w 换根核心公式直接使用匿名函数的陷阱Go 中闭包引用自身时需要先声明变量go// ✅ 正确写法var dfs1 func(int, int) intdfs1 func(u, parent int) int {// 内部可以调用 dfs1}// ❌ 错误写法编译错误dfs1 : func(u, parent int) int {// 这里 dfs1 还未定义dfs1(v, u) // 编译错误}更简洁的写法避免显式声明如果不想声明两次可以用普通函数替代匿名函数gofunc minEdgeReversals(n int, edges [][]int) []int {g : make([][][2]int, n)for i : 0; i n; i {g[i] make([][2]int, 0)}for _, e : range edges {u, v : e[0], e[1]g[u] append(g[u], [2]int{v, 1})g[v] append(g[v], [2]int{u, -1})}ans : make([]int, n)// 独立函数更清晰var dfs1 func(int, int) intdfs1 func(u, parent int) int {res : 0for _, edge : range g[u] {v, w : edge[0], edge[1]if v parent {continue}if w -1 {res}res dfs1(v, u)}return res}ans[0] dfs1(0, -1)var dfs2 func(int, int)dfs2 func(u, parent int) {for _, edge : range g[u] {v, w : edge[0], edge[1]if v parent {continue}ans[v] ans[u] wdfs2(v, u)}}dfs2(0, -1)return ans}复杂度分析· 时间复杂度O(n)每个节点和每条边遍历两次· 空间复杂度O(n)邻接表 递归栈最坏O(n)示例验证gon : 4edges : [][]int{{2,0}, {2,1}, {1,3}}// 输出[1,1,0,2]fmt.Println(minEdgeReversals(n, edges))