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