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

下面是 LeetCode 2858 的 C 语言实现采用换根 DP 算法。c/*** Note: The returned array must be malloced, assume caller calls free().*/// 邻接表结点typedef struct EdgeNode {int to; // 目标结点int weight; // 权重1 表示原边 u-v-1 表示原边 v-ustruct EdgeNode *next;} EdgeNode;// 添加带权边头插法void addEdge(EdgeNode **head, int to, int weight) {EdgeNode *node (EdgeNode*)malloc(sizeof(EdgeNode));node-to to;node-weight weight;node-next *head;*head node;}// 第一次 DFS以 0 为根计算需要反转的边数int dfs1(EdgeNode **graph, int u, int parent) {int res 0;EdgeNode *p graph[u];while (p) {int v p-to, w p-weight;if (v ! parent) {// 如果权重是 -1说明原边方向是 v-u从 u 出发需要反转if (w -1) res;res dfs1(graph, v, u);}p p-next;}return res;}// 第二次 DFS换根计算所有结点的答案void dfs2(EdgeNode **graph, int *ans, int u, int parent) {EdgeNode *p graph[u];while (p) {int v p-to, w p-weight;if (v ! parent) {// 核心转移ans[v] ans[u] wans[v] ans[u] w;dfs2(graph, ans, v, u);}p p-next;}}int* minEdgeReversals(int n, int** edges, int edgesSize, int* edgesColSize, int* returnSize) {// 1. 分配邻接表数组长度为 n每个元素是头指针EdgeNode **graph (EdgeNode**)calloc(n, sizeof(EdgeNode*));// 2. 建图每条无向边存储为两条带权有向边for (int i 0; i edgesSize; i) {int u edges[i][0];int v edges[i][1];// 原边方向 u - v权重 1addEdge(graph[u], v, 1);// 反向边 v - u权重 -1addEdge(graph[v], u, -1);}// 3. 分配结果数组int *ans (int*)malloc(n * sizeof(int));*returnSize n;// 4. 第一次 DFS从结点 0 出发计算反转次数ans[0] dfs1(graph, 0, -1);// 5. 第二次 DFS换根计算所有结点dfs2(graph, ans, 0, -1);// 6. 释放邻接表内存for (int i 0; i n; i) {EdgeNode *p graph[i];while (p) {EdgeNode *tmp p;p p-next;free(tmp);}}free(graph);return ans;}代码说明部分 解释EdgeNode 邻接表结点存储目标结点、权重1/-1和 next 指针addEdge 头插法加入带权边dfs1 以结点 0 为根统计所有需要反转的边权重为 -1 的边dfs2 换根 DPans[child] ans[parent] weight(parent→child)main 函数未列出 按 LeetCode 格式直接提交上述函数即可核心算法1. 建图技巧原边 u - v 拆分为两条带权有向边· u - v 权重 1表示从 u 出发无需反转· v - u 权重 -1表示从 v 出发需要反转一次2. 第一次 DFS从任意根如 0出发计算需要反转的边数 所有权重为 -1 的边的个数。3. 换根公式已知 ans[parent]当根从 parent 移动到 child 时· 若原边方向为 parent - child权重 1则从 child 出发需要多反转 1 次才能回到 parent。· 若原边方向为 child - parent权重 -1则从 child 出发可少反转 1 次。因此ans[child] ans[parent] weight(parent→child)。复杂度分析· 时间O(n)每条边被访问常数次。· 空间O(n)邻接表存储 2*(n-1) 条边 递归栈最坏 O(n)。测试示例c// 输入n 4, edges [[2,0],[2,1],[1,3]]// 输出[1,1,0,2]直接提交上述代码即可通过。