বাইনারি ট্রিতে পারফেক্ট স্কয়ার ওজন বিশিষ্ট নোড গণনা C++-এ

একটি বাইনারি ট্রি দেওয়া আছে যার নোডগুলোর ওজন সংখ্যা হিসেবে আছে। লক্ষ্য হলো সেই নোডগুলোর সংখ্যা বের করা যাদের ওজন একটি পারফেক্ট স্কয়ার। যদি ওজন ৩৬ হয় তবে সেটি ৬², সুতরাং নোডটি গণনা হবে।

ইনপুট

ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes whose weight is a perfect square are: 4

ব্যাখ্যা

আমাদের ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত ওজন দেওয়া আছে। এখন চেক করা হচ্ছে নোডগুলোর ডিজিটগুলো পারফেক্ট স্কয়ার কিনা।

ইনপুট

ইনপুট ভ্যালুগুলো থেকে যে ট্রি তৈরি হবে वो নিচে দেওয়া আছে:

আউটপুট

Count the nodes whose weight is a perfect square are: 2

ব্যাখ্যা

আমাদের ট্রি নোডগুলো এবং প্রতিটি নোডের সাথে যুক্ত ওজন দেওয়া আছে। এখন চেক করা হচ্ছে নোডগুলোর ডিজিটগুলো পারফেক্ট স্কয়ার কিনা।

প্রোগ্রামে ব্যবহৃত পদ্ধতি:

এই পদ্ধতিতে আমরা ট্রির গ্রাফে DFS অ্যাপ্লাই করি ট্রভারস করতে এবং চেক করি নোডের ওजन পারফেক্ট স্কয়ার কিনা। দুটি ভেক্টর Node_Weight(100) এবং edge_graph[100] নেওয়া হয়।

• Node_Weight[] নোডের ওজন দিয়ে ইনিশিয়ালাইজ করা হয়।
• edge_graph ভেক্টর দিয়ে ট্রি তৈরি করা হয়।
• গ্লোবাল ভেরিয়েবল square ০ দিয়ে ইনিশিয়ালাইজ।
• check(int check_it) ফাংশন ইন্টিজার নিয়ে পারফেক্ট স্কয়ার কিনা চেক করে।
• total = sqrt(check_it) এবং floor(total) != ceil(total) হলে false, অন্যথায় true।
• perfect_square(int node, int root) ফাংশন নোড এবং রুট নোড নিয়ে পারফেক্ট স্কয়ার ওজন বিশিষ্ট নোড কাউন্ট রিটার্ন করে।
• check(Node_Weight[node]) true হলে square++।
• edge_graph[node] ট্রভারস করে রিকারসিভ কল perfect_square(it, node)।
• শেষে square ভেরিয়েবলে প্রয়োজনীয় কাউন্ট পাওয়া যায়।

উদাহরণ

#include <bits/stdc++.h>
using namespace std;

vector<int> Node_Weight(100);
vector<int> edge_graph[100];
int square = 0;

bool check(int check_it) {
    double total = sqrt(check_it);
    if (floor(total) != ceil(total)) {
        return false;
    }
    return true;
}

void perfect_square(int node, int root) {
    if (check(Node_Weight[node])) {
        square++;
    }
    for (int it : edge_graph[node]) {
        if (it == root) {
            continue;
        }
        perfect_square(it, node);
    }
}

int main() {
    // নোডের ওজন
    Node_Weight[2] = 121;
    Node_Weight[1] = 81;
    Node_Weight[4] = 37;
    Node_Weight[3] = 25;
    Node_Weight[8] = 100;
    Node_Weight[9] = 701;
    // গ্রাফ এজ তৈরি
    edge_graph[2].push_back(1);
    edge_graph[2].push_back(4);
    edge_graph[4].push_back(3);
    edge_graph[4].push_back(8);
    edge_graph[8].push_back(9);
    perfect_square(2, 2);
    cout << "Count the nodes whose weight is a perfect square are: " << square;
    return 0;
}

আউটপুট

Count the nodes whose weight is a perfect square are: 4