# 2023-09-03：用go编写。给你一个 n 个节点的无向无根树，节点编号从 0 到

2023-09-03：用go语言编写。给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1

1 表示节点 i 处有一个金币。

# 代码思路：

1.创建图结构和入度数组，并初始化空图和入度数组。

2.遍历边数组，将边的两个节点加入图中，同时更新入度数组。

3.创建队列，并将所有入度为1且节点上金币为0的节点加入队列。

4.使用BFS算法遍历队列，将入度-1并将入度为1且节点上金币为0的相邻节点加入队列。

5.继续遍历队列，将入度-1并记录节点的排名，并将入度为1的相邻节点加入队列。

6.计算满足条件的边数，即排名大于等于2的边。

7.返回计数值作为最少经过的边数。

# go完整代码如下：

``````package main

import "fmt"

func collectTheCoins(coins []int, edges [][]int) int {
n := len(coins)
graph := make([][]int, n)
inDegree := make([]int, n)

for i := 0; i < n; i++ {
graph[i] = []int{}
}

for _, edge := range edges {
graph[edge[0]] = append(graph[edge[0]], edge[1])
graph[edge[1]] = append(graph[edge[1]], edge[0])
inDegree[edge[0]]++
inDegree[edge[1]]++
}

queue := make([]int, n)
l, r := 0, 0

for i := 0; i < n; i++ {
if inDegree[i] == 1 && coins[i] == 0 {
queue[r] = i
r++
}
}

for l < r {
cur := queue[l]
l++
for _, next := range graph[cur] {
if inDegree[next]--; inDegree[next] == 1 && coins[next] == 0 {
queue[r] = next
r++
}
}
}

for i := 0; i < n; i++ {
if inDegree[i] == 1 && coins[i] == 1 {
queue[r] = i
r++
}
}

rank := make([]int, n)

for l < r {
cur := queue[l]
l++
for _, next := range graph[cur] {
if inDegree[next]--; inDegree[next] == 1 {
rank[next] = rank[cur] + 1
queue[r] = next
r++
}
}
}

ans := 0

for _, edge := range edges {
if rank[edge[0]] >= 2 && rank[edge[1]] >= 2 {
ans += 2
}
}

return ans
}

func main() {
coins := []int{1, 0, 0, 0, 0, 1}
edges := [][]int{{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}}

result := collectTheCoins(coins, edges)
fmt.Println(result)
}
``````

# rust完整代码如下：

``````fn collect_the_coins(coins: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
let n = coins.len();
let mut graph: Vec<Vec<i32>> = vec![vec![]; n];
let mut in_degree: Vec<i32> = vec![0; n];

for edge in &edges {
let u = edge[0];
let v = edge[1];
graph[u as usize].push(v);
graph[v as usize].push(u);
in_degree[u as usize] += 1;
in_degree[v as usize] += 1;
}

let mut queue: Vec<i32> = vec![0; n];
let mut l = 0;
let mut r = 0;
for i in 0..n {
if in_degree[i] == 1 && coins[i] == 0 {
queue[r as usize] = i as i32;
r += 1;
}
}

while l < r {
let cur = queue[l as usize];
l += 1;
for &next in &graph[cur as usize] {
in_degree[next as usize] -= 1;
if in_degree[next as usize] == 1 && coins[next as usize] == 0 {
queue[r as usize] = next;
r += 1;
}
}
}

for i in 0..n {
if in_degree[i] == 1 && coins[i] == 1 {
queue[r as usize] = i as i32;
r += 1;
}
}

let mut rank: Vec<i32> = vec![0; n];
while l < r {
let cur = queue[l as usize] as usize;
l += 1;
for &next in &graph[cur] {
in_degree[next as usize] -= 1;
if in_degree[next as usize] == 1 {
rank[next as usize] = rank[cur] + 1;
queue[r as usize] = next;
r += 1;
}
}
}

let mut ans = 0;
for edge in &edges {
let u = edge[0] as usize;
let v = edge[1] as usize;
if rank[u] >= 2 && rank[v] >= 2 {
ans += 2;
}
}

ans
}

fn main() {
let coins = vec![0, 0, 0, 1, 1, 0, 0, 1];
let edges = vec![
vec![0, 1],
vec![0, 2],
vec![1, 3],
vec![1, 4],
vec![2, 5],
vec![5, 6],
vec![5, 7],
];

let result = collect_the_coins(coins, edges);
println!("Result: {}", result);
}
``````

# c++完整代码如下：

``````#include <iostream>
#include <vector>

using namespace std;

int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
int n = coins.size();
vector<vector<int>> graph(n);
vector<int> inDegree(n, 0);
for (auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
inDegree[edge[0]]++;
inDegree[edge[1]]++;
}
vector<int> queue;
int l = 0, r = 0;
for (int i = 0; i < n; ++i) {
if (inDegree[i] == 1 && coins[i] == 0) {
queue.push_back(i);
r++;
}
}
while (l < r) {
int cur = queue[l++];
for (int next : graph[cur]) {
if (--inDegree[next] == 1 && coins[next] == 0) {
queue.push_back(next);
r++;
}
}
}
for (int i = 0; i < n; ++i) {
if (inDegree[i] == 1 && coins[i] == 1) {
queue.push_back(i);
r++;
}
}
vector<int> rank(n, 0);
while (l < r) {
int cur = queue[l++];
for (int next : graph[cur]) {
if (--inDegree[next] == 1) {
rank[next] = rank[cur] + 1;
queue.push_back(next);
r++;
}
}
}
int ans = 0;
for (auto& edge : edges) {
if (rank[edge[0]] >= 2 && rank[edge[1]] >= 2) {
ans += 2;
}
}
return ans;
}

int main() {
vector<int> coins = { 1, 0, 0, 0, 0, 1 };
vector<vector<int>> edges = { {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5} };

int result = collectTheCoins(coins, edges);
cout << result << endl;

return 0;
}``````

# c完整代码如下：

``````#include <stdio.h>
#include <stdlib.h>

int collectTheCoins(int* coins, int coinsSize, int** edges, int edgesSize, int* edgesColSize) {
int n = coinsSize;
int** graph = (int**)malloc(n * sizeof(int*));
int* inDegree = (int*)calloc(n, sizeof(int));

for (int i = 0; i < n; i++) {
graph[i] = (int*)malloc(n * sizeof(int));
}

for (int i = 0; i < edgesSize; i++) {
int v = edges[i][0];
int u = edges[i][1];
graph[v][u] = 1;
graph[u][v] = 1;
inDegree[v]++;
inDegree[u]++;
}

int* queue = (int*)malloc(n * sizeof(int));
int l = 0, r = 0;
for (int i = 0; i < n; ++i) {
if (inDegree[i] == 1 && coins[i] == 0) {
queue[r++] = i;
}
}

while (l < r) {
int cur = queue[l++];
for (int next = 0; next < n; next++) {
if (graph[cur][next] == 1) {
if (--inDegree[next] == 1 && coins[next] == 0) {
queue[r++] = next;
}
}
}
}

for (int i = 0; i < n; ++i) {
if (inDegree[i] == 1 && coins[i] == 1) {
queue[r++] = i;
}
}

int* rank = (int*)calloc(n, sizeof(int));
while (l < r) {
int cur = queue[l++];
for (int next = 0; next < n; next++) {
if (graph[cur][next] == 1) {
if (--inDegree[next] == 1) {
rank[next] = rank[cur] + 1;
queue[r++] = next;
}
}
}
}

int ans = 0;
for (int i = 0; i < edgesSize; i++) {
if (rank[edges[i][0]] >= 2 && rank[edges[i][1]] >= 2) {
ans += 2;
}
}

// 释放动态分配的内存
for (int i = 0; i < n; i++) {
free(graph[i]);
}
free(graph);
free(inDegree);
free(queue);
free(rank);

return ans;
}

int main() {
int coins[] = { 1, 0, 0, 0, 0, 1 };
int* edges[] = {
(int[]) {
0, 1
},
(int[]) {
1, 2
},
(int[]) {
2, 3
},
(int[]) {
3, 4
},
(int[]) {
4, 5
}
};
int coinsSize = sizeof(coins) / sizeof(coins[0]);
int edgesSize = sizeof(edges) / sizeof(edges[0]);
int edgesColSize[] = { 2, 2, 2, 2, 2 };

int result = collectTheCoins(coins, coinsSize, edges, edgesSize, edgesColSize);
printf("Result: %d\n", result);

return 0;
}``````

(=￣ω￣=)··· 暂无内容！

482

23

38

22