You are viewing a single comment's thread. Return to all 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; }
Seems like cookies are disabled on this browser, please enable them to open this website
Even Tree
You are viewing a single comment's thread. Return to all comments →
standard DFS