Đếm nút cây có trọng số là số chính phương trong C++

Cho cây với trọng số nút. Đếm nút có trọng số là số chính phương (ví dụ 36 = 6²).

Ý tưởng

• DFS trên cây (edge_graph, Node_Weight).
• Hàm check(n): tính sqrt(n), nếu floor == ceil thì là chính phương.
• Hàm perfect_square(node, root) đệ quy đếm.

Ví dụ hoàn chỉnh

#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 << "Số nút có trọng số chính phương: " << square;
    return 0;
}

Kết quả

Số nút có trọng số chính phương: 4