Even Tree

You are given a tree (a simple connected graph with no cycles).

Find the maximum number of edges you can remove from the tree to get a forest such that each connected component of the forest contains an even number of nodes.

Example:

Input: t_nodes = 10, t_edges = 9, t_from = {2, 3, 4, 5, 6, 7, 8, 9, 10}, t_to = {1, 1, 3, 2, 1, 2, 6, 8, 8}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1001];
bool visited[1001];
int dist[1001];

//dfs function
void dfs(int n)
{
    //marks as visited
    visited[n] = true;

    //dist of current node as 1
    dist[n] = 1;

    //iterate for adjacency list of
    //the current node
    for (auto i : adj[n])
    {

        //if node viisted then
        if (visited[i] == false)
        {
            //call for dfs
            dfs(i);

            //update the dist
            dist[n] += dist[i];
        }
    }
}
int evenForest(int t_nodes, int t_edges,
               vector<int> t_from, vector<int> t_to)
{

    for (int i = 0; i < t_edges; i++)
    {
        int u = t_from[i];
        int v = t_to[i];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    memset(visited, false, sizeof(visited));
    memset(dist, 0, sizeof(dist));
    dfs(1);
    int cnt = 0;

    for (int i = 2; i <= t_nodes; i++)
    {
        if (dist[i] % 2 == 0)
            cnt++;
    }
    return cnt;
}

int main()
{

    int t_nodes = 10;
    int t_edges = 9;

    vector<int> t_from = {2, 3, 4, 5, 6, 7, 8, 9, 10};
    vector<int> t_to = {1, 1, 3, 2, 1, 2, 6, 8, 8};

    cout << evenForest(t_nodes, t_edges, t_from, t_to) << "\n";

    return 0;
}