algorithm - hackrerank Even tree solution explanation(forest with even number nodes) -

i doing problem named tree on hackerank:

https://www.hackerrank.com/challenges/even-tree

and had no clue how cut edges , build forest out of tree. looked on internet, , saw answer on stackeverflow:

obtain forest out of tree number of nodes

well counting number of children looked simpler, , implemented in c++:

#include <iostream> #include <list> #include <vector> using namespace std;  int main() {   int n, m, ans = 0;   cin >> n >> m;   vector<int> tree(n+1);   vector<int> count(n+1);    fill(count.begin(), count.end(), 1);   for(int = 0; < m; i++) {     int p, q;     cin >> p >> q;     tree[p] = q;      int root = tree[p];      // updating ancesors child count     while(root) {       count[root] += count[p];       root = tree[root];     }   }    int counter = 0;   // displaying results   for(int = 2; < count.size(); i++) {     cout << count[i] << " ";     if(count[i]%2 == 0)       counter++;   }   cout <<"\nans : " <<  counter << endl;   return 0; } 

my question is: how approach work? how number of children associated selection of tree minimum number of edges? don't want copy solution , want understand actual logic behind it. please help

first of all, question said test cases (all input trees), there exists way remove edges size of forest preserved. , of course every tree in result forest of size, means total number of nodes n must even. tree must have solution @ least can remove 0 edge form forests.

notice there edges cannot removed, namely, the edge connecting leaf nodes. therefore greedy thoughts pop in head, , turns out can proof them, become greedy algorithm can solved problem.

---

i claim that

a) subtree of size, can safely remove them original graph reduce problem without affecting result, removing edge of subtree root , parent (if exist)

b) subtree of odd size, can replace whole subtree single node reduce problem. edge of subtree root , parent cannot removed (if exist)

we proof a) contradiction. assume if remove subtree graph make problem solvable unsolvable. consider graph after removing subtree, if of odd size, original graph unsolvable well; if of size, must have solution after removing subtree. both cases yield contradiction.

b) quite straight forward, subtree odd size, parity same single leaf node, must connected parent. can replace subtree single node reduce problem.

---

by a) , b), can greedy algorithm leafs of tree (because know edges connecting leafs must chosen, forming subtrees , can reduce problem starting here)

1. connect leafs parents
2. for subtrees formed, if subtree even, add global answer counter 1 , remove subtree; if subtree odd, replace single node (which leaf now).
3. repeat 2 until @ 1 node left

---

that's it. conceptwise, algorithm.

you can implement using many different methods though, use dfs quite directly translating algorithm code.

some count number of children because can tell if subtree odd or even.

someone count # of nodes has degrees! (this far smartest solution know)

but of them share same concept behind: determine if subtree odd size of size, remove them (and increase answer counter) or replace them single node reduce problem.

all implementation share same complexity o(n) well.

here accepted code:

#include<bits/stdc++.h> using namespace std;  int w[105][105] = {0}, v[105] = {0}; int n,m,ans=0;  int dfs(int x){     v[x] = 1;     int son = 0;     for(int i=0; i<105;i++)          if(w[x][i] && !v[i]) son += dfs(i);     if(son % 2) { ans++; return 0;}     return 1; }  int main() {     scanf("%d%d", &n,&m);     for(int i=0,a,b; i<m;i++){         scanf("%d%d", &a,&b);         w[a][b] = w[b][a] = 1;     }     dfs(1);     printf("%d\n", ans-1);       return 0; }