Even Forests (Graph Theory): Depth First Search Implementation

Problem Statement:

As we all know that Tree is basically a subset of Graph; a simple connected graph with no cycles.A tree with N nodes (numbered as 1,2,3,..,N) has N-1 edges.Forest is created when there exists two or more independent trees in a graph.Forest can be created by removing edges from a tree.

In this problem you will be given a tree with N nodes.You have to remove as many edges from the tree as possible to obtain a forest with condition that : Each connected component of the forest should contain even number of vertices.

Your task is to calculate the number of independent trees in that forest.

Consider that the tree is rooted at 1.

Input:

The first line of the input contains an integer N, where N is the number of nodes in a tree.Following N-1 lines contains two integers X and Y, where X is a child of Y.

Output:

Print the answer, a single integer.

Constraints:

1<=N<=100000
1<=X,Y<=N
                                                                                     
Example:

Input:

10
2 1
3 1
4 3                                          
5 2                                                                                      ORIGINAL TREE
6 1
7 2
8 6
9 8
10 8




Output:                                  
3                                                                              




                                                                                          DECOMPOSED TREE
Algorithm:

The problem can be easily solved using Depth First Search.For every node maintain the count information regarding total number of nodes for which the current node is their ancestor.

Solution:

/*
Problem Description:Even Forests

Submitted By
Arjun Mishra
*/

#include<iostream>
#include<vector>
#define MAX 100001
using namespace std;
vector<int> AdjList[MAX];
int nChild[MAX]={};
int dfs(int source)
{
int len=AdjList[source].size();
if(len==0)
{
nChild[source]=1;
return 1;
}
for(int i=0;i<len;i++)
{
nChild[source]+=(dfs(AdjList[source][i]));
}
nChild[source]+=1;
return nChild[source];
}
int main()
{
    int N,E;
    cin>>N;
    E=N-1;//number of edges in a tree
    while(E--)
    {
        int x,y;
        cin>>x>>y;//x is a child of y
        AdjList[y].push_back(x);
    }  
    //applying dfs
    int source=1,count=0;
    dfs(source);
    //counting ancestors with even number of nodes under them
    for(int i=1;i<=N;i++)
    if(nChild[i]%2==0)
    count++;
    //output, required answer
    cout<<count<<endl;
    return 0;

}