মান লিখুন: আমাদের কাছে N উপাদান বিশিষ্ট দুটি অ্যারে A এবং B আছে। আমল এবং বিমল একটি বোর্ডে খেলছেন যাতে 1 থেকে N পর্যন্ত নম্বর দেওয়া সেল আছে। N-1টি রোড আছে যা দুটি সেল সংযুক্ত করে। i-তম রোড A[i]-কে B[i]-এর সাথে সংযুক্ত করে। যেকোনো সেল যেকোনো অন্য সেল থেকে পৌঁছানো যায়। শুরুতে সেল ১ কালো রঙের, এবং সেল N সাদা রঙের। বাকি সেলগুলো রঙীন নয়। আমল প্রথম খেলে, তারপর তারা বালীল বালীল খেলে। আমল একটি অনরঙীন সেল নির্বাচন করে যা কালো সেলের সাথে সন্নিহিত এবং সেটি কালো রঙ দেয়। বিমল একটি অনরঙীন সেল নির্বাচন করে যা সাদা সেলের সাথে সন্নিহিত এবং সেটি সাদা রঙ দেয়। যেনে খেলোয়ার কাউকে রঙ দিতে না পারলে সে হারে। বিজয়ী কে তা বের করতে হবে।
উদাহরণ
যদি ইনপুট হয় A = [3, 1, 3, 7, 5, 1]; B = [6, 2, 1, 4, 7, 4], তবে আউটপুট হবে "Amal", কারণ আমল যদি প্রথমে সেল ২ কালো করে, তবে বিমল যেভাবে খেলুক না কেন আমল জিতবে।
সমাধানের ধাপসমূহ
N := 99999
adjList এডজেসেন্সি লিস্ট
p, d, ssz অ্যারে
dfs(nd, par, dep) ফাংশন:
p[nd] := par
d[nd] := dep
ssz[nd] := 1
adjList[nd]-এর প্রতিটি নোড i এর জন্য:
যদি i XOR par নন-জিরো:
dfs(i, nd, dep+1)
ssz[nd] := ssz[nd] + ssz[i]
মূল ফাংশন:
n := A এর আকার
for i := 1 থেকে n-1:
u := A[i-1], v := B[i-1]
adjList[u]-তে v যোগ করুন
adjList[v]-তে u যোগ করুন
dfs(1, 1, 0)
nd := n
for i := 0 থেকে (d[n]-1)/2 - 1:
nd := p[nd]
যদি 2*ssz[nd] >= n: "Bimal" রিটার্ন করুন
অন্যথায়: "Amal" রিটার্ন করুন
C++ বাস্তবায়ন
#include <bits/stdc++.h>
using namespace std;
int N = 99999;
vector<vector<int>> adjList(N);
vector<int> p(N), d(N), ssz(N);
void dfs(int nd, int par, int dep) {
p[nd] = par;
d[nd] = dep;
ssz[nd] = 1;
for (int i : adjList[nd]) {
if (i ^ par) {
dfs(i, nd, dep + 1);
ssz[nd] += ssz[i];
}
}
}
string solve(vector<int> A, vector<int> B) {
int n = A.size();
for (int i = 1; i < n; i++) {
int u = A[i - 1], v = B[i - 1];
adjList[u].push_back(v);
adjList[v].push_back(u);
}
dfs(1, 1, 0);
int nd = n;
for (int i = 0; i < (d[n] - 1) / 2; i++)
nd = p[nd];
return (2 * ssz[nd] >= n ? "Bimal" : "Amal");
}
int main() {
vector<int> A = { 3, 1, 3, 7, 5, 1 };
vector<int> B = { 6, 2, 1, 4, 7, 4 };
cout << solve(A, B) << endl;
}
ইনপুট
{ 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 }
আউটপুট
Amal
