HackerRank Deforestation problem solution

In this HackerRank Deforestation problem solution Alice and Bob are playing a game with a rooted tree. The tree has N vertices and the first node, 1, is always the root. Here are the basic rules:

Alice always makes the first move.

They move in alternating turns, and both players always move optimally.

During each move, a player removes an edge from the tree, disconnecting one of its leaves or branches. The leaf or branch that was disconnected from the rooted tree is removed from the game.

The first player to be unable to make a move loses the game.

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 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()

Deforestation 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;
}