उस नोड का पता लगाएं जिसका एक्स के साथ पूर्ण अंतर सी ++ में अधिकतम मूल्य देता है

मान लीजिए कि हमारे पास एक पेड़ है, और सभी नोड्स का वजन और एक पूर्णांक x है। हमें नोड i को खोजना है, जैसे |वेट[i] - x| न्यूनतम है। यदि ग्राफ नीचे जैसा है, और x =15

आउटपुट 3 होगा। अब विभिन्न नोड्स के लिए, यह नीचे जैसा होगा

नोड 1, |5 - 15| =10

नोड 2, |10 - 15| =5

नोड 3, |11 - 15| =4

नोड 4, |8 - 15| =7

नोड 5, |6 - 15| =9

विचार सरल है। हम पेड़ पर डीएफएस करेंगे, और नोड का ट्रैक रखेंगे, जिसका भारित निरपेक्ष अंतर 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