HackerRank Deforestation problem solution

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.

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("Bobn");
        else printf("Alicen");
    }
    return 0;
}