• + 0 comments

    standard DFS

    int descendents(int current, const vector<vector<int>>& edges, int& components, vector<bool>& visited, vector<int>& size) {
        visited[current] = true;
        for (auto e : edges[current]) {
            if (!visited[e]) {
                size[current] = size[current] + descendents(e, edges, components, visited, size);;
            }
        }
        ++size[current];
        if (current != 1 and size[current] % 2 == 0) {
            ++components;
            return 0;
        }
        else return size[current];
    }
    
    int evenForest(int N, int E, const vector<vector<int>>& edges) {
        int components = 0;
        vector<bool> visited(N+1);
        vector<int> size(N+1);
        descendents(1, edges, components, visited, size);    
        return components;
    }