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.

As an example, the following tree with nodes can be cut at most time to create an even forest.

Function Description

Complete the evenForest function in the editor below. It should return an integer as described.

evenForest has the following parameter(s):

• t_nodes: the number of nodes in the tree
• t_edges: the number of undirected edges in the tree
• t_from: start nodes for each edge
• t_to: end nodes for each edge, (Match by index to t_from.)

Input Format

The first line of input contains two integers and , the number of nodes and edges.
The next lines contain two integers and which specify nodes connected by an edge of the tree. The root of the tree is node .

Constraints

Note: The tree in the input will be such that it can always be decomposed into components containing an even number of nodes. is the set of positive even integers.

Output Format

Print the number of removed edges.

solution

By Chanupa Gurusinghe

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

#include <vector>
using namespace std;

int dfs(int node, vector<vector<int>>& adj, int& removableEdges, vector<bool>& visited) {
    visited[node] = true;
    int subtreesize = 1;

    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
           int childsize = dfs(neighbor, adj, removableEdges, visited);

           if (childsize % 2 == 0) {
               removableEdges++;
           }
           else {
               subtreesize += childsize;
           }
        }
    }
    return subtreesize;
}

int evenForest(int t_nodes, int t_edges, vector<int> t_from, vector<int> t_to) {
    vector<vector<int>> adj(t_nodes + 1);
    for (int i = 0; i < t_edges; i++) {
        adj[t_from[i]].push_back(t_to[i]);
        adj[t_to[i]].push_back(t_from[i]);
    }

    vector<bool> visited(t_nodes + 1, false);
    int removableEdges = 0;

    dfs(1, adj, removableEdges, visited);
    return removableEdges;
}


int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string t_nodes_edges_temp;
    getline(cin, t_nodes_edges_temp);

    vector<string> t_nodes_edges = split(rtrim(t_nodes_edges_temp));

    int t_nodes = stoi(t_nodes_edges[0]);
    int t_edges = stoi(t_nodes_edges[1]);

    vector<int> t_from(t_edges);
    vector<int> t_to(t_edges);

    for (int i = 0; i < t_edges; i++) {
        string t_from_to_temp;
        getline(cin, t_from_to_temp);

        vector<string> t_from_to = split(rtrim(t_from_to_temp));

        int t_from_temp = stoi(t_from_to[0]);
        int t_to_temp = stoi(t_from_to[1]);

        t_from[i] = t_from_temp;
        t_to[i] = t_to_temp;
    }

    int res = evenForest(t_nodes, t_edges, t_from, t_to);

    fout << res << "\n";

    fout.close();

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}