HackerrankInterviewQuestions | Lei Jiang Coding

HackerrankInterviewQuestions | Lei Jiang Coding
You are given a tree (a simple connected graph with no cycles). You have to remove as many edges from the tree as possible to obtain a forest with the condition that : Each connected component of the forest should contain an even number of vertices.
To accomplish this, you will remove some edges from the tree. Find out the number of removed edges.

the input graph will be such that it can always be decomposed into components containing even number of nodes which indirectly means that N is even.
https://www.hackerrank.com/challenges/even-tree/editorial

vector<int> al[105];
bool visit[105];
int n,m;
int ans;

int dfs(int node)
{
    visit[node]=true;
    int num_vertex=0;
    for(int i=0;i<al[node].size();i++)
    {
        if(!visit[al[node][i]])
        {
            int num_nodes=dfs(al[node][i]);
            if(num_nodes%2==0)
                ans++;
            else
                num_vertex+=num_nodes;
        }
    }
    return num_vertex+1;
}

On removing edges (1, 3) and (1, 6), we can get the desired result.

Original tree:

Decomposed tree:

int main() {
    int N, M;
    cin >> N >> M;
    unordered_map<int, vector<int> > vertix;
    for(int i = 0; i < M; ++i){
        int v, e;
        cin >> v >> e;
        vertix[e].push_back(v);
    }
    int res = 0;
    for(int i = N; i > 1; --i){
        if (vertix[i].size()){
            deque<int> q;
            int count = 0; 
            q.push_back(i);
            while(!q.empty()){
                int node = q.front();
                q.pop_front();
                count++;
                for(int j = 0; j < vertix[node].size(); ++j)
                    q.push_back(vertix[node][j]);
            }
            if (count % 2 == 0)
                ++res;
        }
        
    }
    cout << res << endl;    
    return 0;
}

http://rootchutney.blogspot.com/2014/10/even-tree.htmlRead full article from HackerrankInterviewQuestions | Lei Jiang Coding