Algorithm

HackerRank/Algorithms/Graphy Theory/Even Tree

Problem Summary

Given a tree with N nodes, find the maximum number of edges that can be removed from it to get a forest such that each tree of the forest contains an even number of nodes.

Solution

Apparently, the answer is 0 if n is odd. So we only need to consider when n is even.

First, we can use DFS to calculate the number of children of each node. (Assume node 1 is root.)

Then we do another DFS to try to greedily cut edges. That is, for an edge (x,y), we cut it and increase the answer by 1, whenever the number of children of node y is even.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
nclude <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 120;
int n,ans=0;
int g[maxn][maxn],children[maxn];
bool vis[maxn];
void calc(int x)
{
	vis[x]=true;
	children[x]=1;
	for(int i=1;i<=g[x][0];i++)
	{
		int y=g[x][i];
		if(!vis[y])
		{
			calc(y);
			children[x]+=children[y];
		}
	}
}
void cut(int x)
{
	vis[x]=true;
	for(int i=1;i<=g[x][0];i++)
	{
		int y=g[x][i];
		if(!vis[y])
		{
			if(children[y]%2==0)
			{
				children[x]-=children[y];
				ans++;
			}
			cut(y);
		}
	}
}
int main() {
	int p,a,b;
	scanf("%d%d",&n,&p);
	if(n%2!=0)
	{
		printf("0\n");
		return 0;
	}
	for(int i=0;i<p;i++)
	{
		scanf("%d%d",&a,&b);
		g[a][0]++;
		g[a][g[a][0]]=b;
		g[b][0]++;
		g[b][g[b][0]]=a;
	}
	calc(1);
	memset(vis,0,sizeof(vis));
	cut(1);
	printf("%d\n",ans);
    return 0;
}