LeetCode 2858. 可以到达每一个节点的最少边反转次数 C#
原题链接
困难
作者:
hpstory
,
2023-09-21 17:03:24
,
所有人可见
,
阅读 78
C# 代码
public class Solution {
public int[] MinEdgeReversals(int n, int[][] edges) {
List<List<Node>> graph = new();
for (int i = 0; i < n; i++){
graph.Add(new List<Node>());
}
foreach (int[] edge in edges){
graph[edge[0]].Add(new Node(edge[1], 1));
graph[edge[1]].Add(new Node(edge[0], -1));
}
int[] result = new int[n];
DFS(0, -1);
void DFS(int x, int fa){
foreach (var i in graph[x]){
if (i.w != fa){
if (i.d == -1) result[0]++;
DFS(i.w, x);
}
}
}
DFS2(0, -1);
void DFS2(int x, int fa){
foreach (var i in graph[x]){
if (i.w != fa){
result[i.w] = result[x] + i.d;
DFS2(i.w, x);
}
}
}
return result;
}
public struct Node{
public int w;
public int d;
public Node(int w, int d){
this.w = w;
this.d = d;
}
}
}