在偶数个节点中打破树

Question

给你一棵树（没有环的简单连通图）。

找到可以从树中删除的最大边数以获得森林，使得森林的每个连接组件包含偶数个节点。

https://www.hackerrank.com/challenges/even-tree/problem

上面link给出了测试用例。对于示例输入 1，我得到 0 作为输出而不是预期值 2。

#include<stdio.h>
#include<stdlib.h>
int ans = 0;
int v, e;
int visited[201];
int gph[201][201];

int dfs(int i) {
    int num_nodes;
    int num_vertex = 0;
    visited[i] = 1;
    for (int j = 1; j <= v; j++) {
        if (visited[i] == 0 && gph[i][j] == 1) {
            num_nodes = dfs(j);
            if (num_nodes % 2 == 0)
                ans++;
            else
                num_vertex += num_nodes;
        }
    }
    return num_vertex + 1;
}

int main() {
    scanf("%d %d", &v, &e); // vertices and edges
    int u, v;
    for (int i = 0; i < e; i++) {
        scanf("%d %d", &u, &v); //edges of undirected graph
        gph[u][v] = 1;
        gph[v][u] = 1;
    }
    dfs(1);
    printf("%d", ans);
}

Test case:

10 9 2 1 3 1 4 3 5 2 6 1 7 2 8 6 9 8 10 8

• 预期输出：2

• 实际输出：0

Answer 1

有错字。 if子句中的条件表达式

if (visited[i] == 0 && gph[i][j] == 1)

应该是

if (visited[j] == 0 && gph[i][j] == 1)

顺便说一句，hackrank 问题中的约束条件是 2 <= n <= 100，因此您绝对不需要大小为 201 的固定数组。

Answer 2

// ans is total number of edges removed and al is adjacency list of the tree.
int dfs(int node) 
{
    visit[node]=true;
    int num_vertex=0;
    for(int i=0;i<al[node].size();i++)
    {
        if(!visit[al[node][i]])
        {
            int num_nodes=dfs(al[node][i]);
            if(num_nodes%2==0)
                ans++;
            else
                num_vertex+=num_nodes;
        }
    }
    return num_vertex+1; 
}