นับโหนดที่น้ำหนักเป็นจำนวนกำลังสองสมบูรณ์ (Perfect Square) ใน C++

โจทย์: ให้ Binary Tree ที่โหนดมีน้ำหนักเป็นจำนวนเต็ม ต้องการนับโหนดที่น้ำหนักเป็นกำลังสองสมบูรณ์ (เช่น 1, 4, 9, 16, 25, 36...)

การตรวจสอบกำลังสองสมบูรณ์

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

DFS นับโหนด

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

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);
    }
}

ตัวอย่างเต็ม

#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;  // 11²
    Node_Weight[1] = 81;   // 9²
    Node_Weight[4] = 37;   // ไม่ใช่
    Node_Weight[3] = 25;   // 5²
    Node_Weight[8] = 100;  // 10²
    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: " << square;
    return 0;
}

ผลลัพธ์

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

โหนดที่เป็นกำลังสอง: 121, 81, 25, 100 = 4 โหนด