In this HackerRank Even Tree problem solution 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.
Problem solution in Python.
#!/usr/bin/python3 from collections import deque tree_length, edges = map(int, input().strip().split()) tree = [list() for i in range(tree_length)] for i in range(edges): parent, child = map(int, input().strip().split()) parent -= 1 child -= 1 tree[parent].append(child) tree[child].append(parent) def reconstruct(tree): visited = [False] * len(tree) queue = deque([0]) reconstructed = [list() for i in range(len(tree))] while len(queue) > 0: current = queue.popleft() visited[current] = True for i in tree[current]: if not visited[i]: reconstructed[current].append(i) queue.append(i) return reconstructed cuts = 0 def dfs(tree, index): global cuts subtrees = [] for i in tree[index]: subtrees.append(dfs(tree, i)) for vertices in subtrees[:]: if not vertices % 2: cuts += 1 subtrees.remove(vertices) return sum(subtrees) + 1 tree = reconstruct(tree) dfs(tree, 0) print(cuts)
Problem solution in Java.
import java.io.*;
import java.util.*;
public class Solution {
static class Node {
int name;
Node parent;
List<Node> children;
boolean odd=true;
}
Node[] buildTree(int numEdges, int[][] edgeData) {
Node[] nodes = new Node[numEdges+1+1];
for (int i=0; i<edgeData.length; i++) {
int child = edgeData[i][0];
int parent = edgeData[i][1];
if (nodes[child] == null) {
nodes[child] = new Node();
nodes[child].name=child;
}
if (nodes[parent] == null) {
nodes[parent] = new Node();
nodes[parent].name=parent;
}
nodes[child].parent = nodes[parent];
if (nodes[parent].children == null) {
nodes[parent].children = new ArrayList<Node>();
}
nodes[parent].children.add(nodes[child]);
}
return nodes;
}
int dowork(int numEdges, int[][] edgeData) {
Node[] nodes = buildTree(numEdges, edgeData);
return makeEvenTrees(nodes[1]); // nodes[0] is not used, so that it's easy to keep track of node names..
}
int makeEvenTrees(Node node) {
if (node == null) {
return 0;
}
int numCuts=0;
if (node.children == null) {
return 0; //no cut
} else {
for (Node child : node.children) {
numCuts += makeEvenTrees(child);
if (child.odd) {
node.odd ^= child.odd;
} else {
numCuts += 1;
}
}
}
return numCuts;
}
public static void main(String[] args) {
Solution soln = new Solution();
try (Scanner scan = new Scanner(System.in)) {
int numNodes = scan.nextInt();
int numEdges = scan.nextInt();
int[][] edgeData = new int[numEdges][2];
for (int i = 0; i < numEdges; i++) {
edgeData[i][0] = scan.nextInt();
edgeData[i][1] = scan.nextInt();
}
int result = soln.dowork(numEdges, edgeData);
System.out.println(result);
}
}
}Problem solution in C++.
#include <iostream>
#include <string.h>
#include <map>
#include <string>
#include <set>
#include <vector>
using namespace std;
int vis[110];
vector<int> vec[104];
vector<int> vec2[104];
int le[110];
int root[110];
void dfs(int t)
{
vis[t]=1;
bool tag=0;
for(int i=0;i<vec[t].size();i++)
{
if(vis[vec[t][i]]==0)
{
root[vec[t][i]]=t;
tag=1;
vec2[t].push_back(vec[t][i]);
dfs(vec[t][i]);
}
}
if(tag==0)le[t]=1;
}
int mark[110],ret;
bool ischildallleaf(int i)
{
for(int j=0;j<vec2[i].size();j++)
{
int t=vec2[i][j];
if(mark[t]==0&&le[t]==0)return false;
}
return true;
}
int countt(int i)
{
int cnt=0;
for(int j=0;j<vec2[i].size();j++)
{
int t=vec2[i][j];
if(mark[t]==0)cnt++;
}
return cnt;
}
void colo(int i)
{
mark[i]=1;
for(int j=0;j<vec2[i].size();j++)
{
int t=vec2[i][j];
mark[t]=1;
}
return ;
}
int main()
{
int n,m,i,j,p,q,ta,tb;
cin>>n>>m;
if(n-1!=m)while(1);
memset(vis,0,sizeof(vis));
for(i=1;i<=n;i++){vec[i].clear();vec2[i].clear();}
for(i=1;i<n;i++)
{
cin>>p>>q;
vec[p].push_back(q);
vec[q].push_back(p);
}
memset(le,0,sizeof(le));
root[1]=0;
dfs(1);
memset(mark,0,sizeof(mark));
ret=0;
int nn=n;
while(nn>1)
{
for(i=1;i<=n;i++)
{
if(!mark[i]&&le[i]&&root[i]!=0&&ischildallleaf(root[i]))
{
int t=countt(root[i]);
if(t%2==1)
{
ret++;
colo(root[i]);
if(root[i]!=0&&root[root[i]]!=0)
{
ta=0;
tb=root[root[i]];
for(j=0;j<vec2[tb].size();j++)
{
int r=vec2[tb][j];
if(mark[r]==0)ta=1;
}
if(ta==0)le[tb]=1;
}
}
else
{
colo(root[i]);
mark[root[i]]=0;
le[root[i]]=1;
}
nn=0;
for(j=1;j<=n;j++)if(mark[j]==0)nn++;
break;
}
}
//if(i==n+1)break;
}
cout<<--ret<<endl;
}Problem solution in C.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int vertex;
struct node *down;
struct node *right;
};
struct node *first;
int ret=0,count=0;
int dfs(int i,int n)
{
int j,x;
struct node *val,*hold;
val=first;
for(j=0;j<n;j++)
{
if(val->vertex==i)
{
count++;
//printf("\n Val of count is %d val of i is %d\n",count,i);
hold=val->right;
while(hold!=NULL)
{
x=hold->vertex;
hold=hold->right;
ret=dfs(x,n);
}
break;
}
else
val=val->down;
}
return count;
}
int main()
{
int n,i,j,m,vi,vj,flag=1,p=0;
struct node *loc,*val,*new,*ben,*hold;
int *b;
//printf("Enter the no of vertices\n");
scanf("%d %d",&n,&m);
b=(int *)malloc(n*sizeof(int));
loc=(struct node*)malloc(sizeof(struct node));
loc->vertex=1;
loc->down=NULL;
loc->right=NULL;
first=loc;
val=loc;
for(i=2;i<=n;i++)
{
loc=(struct node*)malloc(sizeof(struct node));
loc->vertex=i;
loc->right=NULL;
val->down=loc;
val=loc;
}
loc->down=NULL;
//printf("Give the no of edges \n");
//scanf(" %d",&m);
for(i=0;i<m;i++)
{
//printf("Give the edge source->destination Vi->Vj \n");
scanf("%d %d",&vi,&vj);
loc=(struct node*)malloc(sizeof(struct node));
loc->right=NULL;
loc->down=NULL;
loc->vertex=vi;
val=first;
for(j=1;j<=n;j++)
{
if(flag==1)
{
if(val->vertex==vj )
{
hold=val;
if(hold->right==NULL)
hold->right=loc;
else
{
ben=hold->right;
hold->right=loc;
loc->right=ben;
}
flag=0;
}
else
val=val->down;
}
}
flag=1;
}
val=first;
for(i=1;i<=n;i++)
{
hold=val;
while(hold!=NULL)
{
//printf("%d",hold->vertex);
hold=hold->right;
}
//printf("\n");
val=val->down;
}
for(i=2;i<=n;i++)
{
count=0;
b[i]=dfs(i,n);
//printf(" %d final %d \n",b[i],i);
}
for(i=2;i<=n;i++)
{
if(b[i]%2==0)
p++;
}
printf("%d",p);
return 0;
}
0 Comments