একটি n-ary ট্রি দেওয়া আছে। প্রতিটি নোডের সাবট্রি-এ কতগুলো লিফ নোড আছে, তা বের করতে হবে।
উদাহরণ: N=8, tree=[[2,3],[],[4,5,6],[7,8],[],[],[],[]] হলে আউটপুট: 1->5, 2->1, 3->4, 4->2, 5->1, 6->1, 7->1, 8->1
অ্যালগরিদম
- n-ary ট্রি আডজেসেন্সি লিস্টে তৈরি করুন
- DFS ট্রাভার্সাল করুন
- leaf[] অ্যারে রাখুন প্রতিটি নোডের লিফ কাউন্ট
- রিকার্সিভ কলের পর leaf[node] += leaf[child]
- যদি চাইল্ড নেই, leaf[node] = ১
- সব নোডের leaf কাউন্ট প্রিন্ট করুন
ইমপ্লিমেন্টেশন
#include <bits/stdc++.h> using namespace std; void insertNode(int x, int y, vector<int> tree[]) { tree[x].push_back(y); } void DFS(int node, int leaf[], int visited[], vector<int> tree[]) { leaf[node] = 0; visited[node] = 1; for (auto it : tree[node]) { if (!visited[it]) { DFS(it, leaf, visited, tree); leaf[node] += leaf[it]; } } if (!tree[node].size()) leaf[node] = 1; } int main() { int N = 8; vector<int> tree[N + 1]; insertNode(1, 2, tree); insertNode(1, 3, tree); insertNode(3, 4, tree); insertNode(3, 5, tree); insertNode(3, 6, tree); insertNode(4, 7, tree); insertNode(4, 8, tree); int leaf[N + 1]; int visited[N + 1]; for (int i = 0; i <= N; i++) visited[i] = 0; DFS(1, leaf, visited, tree); for (int i = 1; i <= N; i++) cout << i << "->" << leaf[i] << endl; return 0; }আউটপুট
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1
