even tree.cpp

#include <iostream>
#include <list>
#include <vector>

using namespace std;

class graph
{
    vector<list<int>> edges;
    
    int dftCountEdges(int b, vector<bool>& visited, int& removalsPossible)
    {
        int edgesInTree = 0;
        visited.at(b) = true;
        for (auto it = edges.at(b).begin(); it != edges.at(b).end(); ++it)
        {
            if (!visited.at(*it))
            {
                int edgesInSub = 0;
                ++edgesInTree;
                edgesInSub = dftCountEdges(*it, visited, removalsPossible);
                if (edgesInSub > 0 && edgesInSub % 2 != 0)
                    ++removalsPossible;
                edgesInTree += edgesInSub;
                
            }
        }
        return edgesInTree;
    }
    
public:
    graph(unsigned long size) : edges { size, list<int>{} } {}
    
    void addEdge(int from, int to)
    {
        //transpose to 0 based vertices.
        
        edges.at(from - 1).push_back(to - 1);
        edges.at(to - 1).push_back(from - 1);
    }
    
    int countRemovals()
    {
        int removalsPossible = 0;
        vector<bool> visited ( edges.size(), false );
        dftCountEdges(0, visited, removalsPossible);
        return removalsPossible;
    }
};

int main() {
    ios_base::sync_with_stdio(false);

    unsigned int n, m;
    
    cin >> n >> m;
    
    graph tree{n};
    
    while (m--)
    {
        int f, t;
        cin >> f >> t;
        tree.addEdge(f, t);
    }
    
    cout << tree.countRemovals();
    return 0;
}