C# 代码
public class Solution {
public int CollectTheCoins(int[] coins, int[][] edges) {
int n = coins.Length;
// 用hashset代替统计入度的列表
List<HashSet<int>> graph = new List<HashSet<int>>();
int result = n - 1;
for (int i = 0; i <= n; i++){
graph.Add(new HashSet<int>());
}
foreach (int[] edge in edges){
graph[edge[0]].Add(edge[1]);
graph[edge[1]].Add(edge[0]);
}
// 第一轮拓扑排序,删除没有金币的子树
Queue<int> queue = new Queue<int>();
for (int i = 0; i <= n; i++){
if (graph[i].Count == 1 && coins[i] == 0) queue.Enqueue(i);
}
while (queue.Count > 0){
int t = queue.Dequeue();
foreach (int i in graph[t]){
graph[i].Remove(t);
result--;
if (graph[i].Count == 1 && coins[i] == 0){
queue.Enqueue(i);
}
}
}
// 第二轮拓扑排序,删除有金币的叶子节点和该节点相邻的,且删除该节点后入度为1的节点
for (int i = 0; i <= n; i++){
if (graph[i].Count == 1 && coins[i] == 1) queue.Enqueue(i);
}
result -= queue.Count;
foreach (int t in queue){
foreach (int i in graph[t]){
graph[i].Remove(t);
if (graph[i].Count == 1){
result--;
}
}
}
// 树中没有金币会导致结果为负,需要和0取max
return Math.Max(result * 2, 0);
}
}