In this HackerRank Deforestation problem solution we have Given the structure of the tree, determine and print the winner of the game. If Alice wins, print Alice; otherwise print Bob.

HackerRank Deforestation problem solution


Problem solution in Python.

#!/bin/python3

import os
import sys
from functools import lru_cache
#
# Complete the deforestation function below.
#
def deforestation(n, tree):
    
    d = dict()
    for x in tree:
        if x[0] in d:
            d[x[0]].add(x[1])
        else:
            d[x[0]]=set()
            d[x[0]].add(x[1])
        if x[1] in d:
            d[x[1]].add(x[0])
        else:
            d[x[1]]=set()
            d[x[1]].add(x[0])
    dp = [-1 for i in range(n+1)]    
       
    def r(node,prev):
        if dp[node]==-1:
            dp[node]=1
            c = 0
            tmp = []  
            if node in d:  
                for x in d[node]:
                    if x!=prev:
                        
                        tmp.append(1+r(x,node))
                    
            for x in tmp:
                c^=x       
            return c
        else:
            return 0
        
    c = r(1,-1)
    #print(c)
    if c==0:
        return "Bob"
    return "Alice"    

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        n = int(input())

        tree = []

        for _ in range(n-1):
            tree.append(list(map(int, input().rstrip().split())))

        result = deforestation(n, tree)

        fptr.write(result + '\n')

    fptr.close()


Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {
    
    static int numHelper(ArrayList<ArrayList<Integer>> z, int current, int prev) {
    int gate = 0;
    for (Integer i : z.get(current)) {
        if (i != prev) {
            gate ^= 1 + numHelper(z, i, current);
        }
    }
        return gate;
    }   

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int x = in.nextInt(); x>0; x--) {
            int o = in.nextInt();
            ArrayList<ArrayList<Integer>> g = new ArrayList<>();
            for (int i=0; i<o; i++) {
                g.add(new ArrayList<Integer>());
            }
            for (int i=0; i<o-1; i++) {
                int one = in.nextInt()-1;
                int two = in.nextInt()-1;
                g.get(one).add(two);
                g.get(two).add(one);
            }
            if(numHelper(g, 0, -1) == 0){
                System.out.println("Bob");
            }
            else{
                System.out.println("Alice");
            }
        }
    }

}


Problem solution in C++.

#include <bits/stdc++.h>

template<typename T> T gcd(T a, T b) {
    if(!b) return a;
    return gcd(b, a % b);
}
template<typename T> T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

template<typename T> void chmin(T& a, T b) { a = (a > b) ? b : a; }
template<typename T> void chmax(T& a, T b) { a = (a < b) ? b : a; }
int in() { int x; scanf("%d", &x); return x; }

using namespace std;

#ifdef ONLINE_JUDGE
#define debug(args...)
#else
#define debug(args...) fprintf(stderr,args)
#endif

typedef long long Int;
typedef unsigned long long uInt;
typedef unsigned uint;

const int MAXN = 550;

int T, N;
vector<int> G[MAXN];

int dfs(int node, int parent) {
    int x = 0;
    
    for (int i = 0; i < (int) G[node].size(); i++) {
        int u = G[node][i];
        
        if (u != parent) {
            x ^= (dfs(u, node) + 1);
        }
    }
    return x;            
}

int main(void) {
    cin >> T;

    for (int t = 1; t <= T; t++) {
        cin >> N;

        for (int i = 0; i <= N; i++) {
            G[i].clear();
        }

        for (int i = 0; i < N - 1; i++) {
            int U, V;
            cin >> U >> V;

            G[U].push_back(V);
            G[V].push_back(U);
        }

        int val = dfs(1, -1);

        if (val) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }
    }
    return 0;
}


Problem solution in C.

#include<stdio.h>
#define N 1500000

int pool[N],next[N],npool,adj[N];

int getSG(int k,int p){
    int i,acc;
    acc=0;
    for(i=adj[k];i!=-1;i=next[i])
    if(pool[i]!=p)acc^=1+getSG(pool[i],k);
    return acc;
}

int main() {
    int i,ncases,from,to,acc,n;
    for(scanf("%d",&ncases);ncases>0;ncases--){
        scanf("%d",&n);
        n--;
        npool=0;
        for(i=0;i<=n;i++) adj[i]=-1;
        for(i=0;i<n;i++){
            scanf("%d %d",&from,&to);
            from--;
            to--;
            pool[npool]=to;
            next[npool]=adj[from];
            adj[from]=npool;
            npool++;
            pool[npool]=from;
            next[npool]=adj[to];
            adj[to]=npool;
            npool++;
        }
        acc=getSG(0,-1);
        if(acc==0)printf("Bob\n");
        else printf("Alice\n");
    }
    return 0;
}