একটি ট্রি, সকল নোডের ওয়েইট (weight) এবং একটি পূর্ণসংখ্যা x দেওয়া আছে। আমাদের এমন একটি নোড i খুঁজে বের করতে হবে যাতে |weight[i] - x| ন্যূনতম হয়। যদি গ্রাফ নিচের মত হয়, এবং x = 15:
আউটপুট হবে ৩। বিভিন্ন নোডের জন্য মান নিচের মত:
Node 1, |5 – 15| = 10
Node 2, |10 – 15| = 5
Node 3, |11 – 15| = 4
Node 4, |8 – 15| = 7
Node 5, |6 – 15| = 9
আইডিয়া সহজ। ট্রিতে DFS (Depth First Search) করব এবং যেই নোডের ওয়েইটের সাথে x-এর निरপেক্ষ পার্থক্য ন্যূনতম, সেটি ট্র্যাক করব।
উদাহরণ
#include <iostream> #include <vector> #include <cmath> using namespace std; int min_value = INT_MAX, x, result; vector<int> graph[100]; vector<int> weight(100); void dfs(int node, int parent) { if (min_value > abs(weight[node] - x)) { min_value = abs(weight[node] - x); result = node; } for (int to : graph[node]) { if (to == parent) continue; dfs(to, node); } } int main() { x = 15; weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; graph[1].push_back(2); graph[2].push_back(3); graph[2].push_back(4); graph[1].push_back(5); dfs(1, 1); cout << "The node number is: " << result; }আউটপুট
The node number is: 3
