Odtnhj

You are given a tree (a simple connected graph with no cycles).

Find the maximum number of edges you can remove from the tree to get a forest such that each connected component of the forest contains an even number of nodes.

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

In the above link the test cases are given. For sampple input 1, I am getting 0 as output instead of expected value 2.

#include<stdio.h>
#include<stdlib.h>
int ans = 0;
int v, e;
int visited[201];
int gph[201][201];

int dfs(int i) 
 int num_nodes;
 int num_vertex = 0;
 visited[i] = 1;
 for (int j = 1; j <= v; j++) 
 if (visited[i] == 0 && gph[i][j] == 1) 
 num_nodes = dfs(j);
 if (num_nodes % 2 == 0)
 ans++;
 else
 num_vertex += num_nodes;
 
 
 return num_vertex + 1;


int main() 
 scanf("%d %d", &v, &e); // vertices and edges
 int u, v;
 for (int i = 0; i < e; i++) 
 scanf("%d %d", &u, &v); //edges of undirected graph
 gph[u][v] = 1;
 gph[v][u] = 1;
 
 dfs(1);
 printf("%d", ans);

Test case:

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

• Expected output: 2




• Actual output: 0

There is a typo. The condition expression in if clause

if (visited[i] == 0 && gph[i][j] == 1)

should be

if (visited[j] == 0 && gph[i][j] == 1)

BTW, the constraints in hackrank question is 2 <= n <= 100, so you definitely don't need a fixed array of size 201.

// ans is total number of edges removed and al is adjacency list of the tree.
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;