C++で重みが完全平方数となるノードを数える方法

各ノードに重みが割り当てられた二分木が与えられたとき、「重みが完全平方数であるノード」の個数を求めるのが本記事の目的です。例えば、あるノードの重みが36であれば、36 = 6² と表せるため、このノードはカウント対象となります。

例

入力

値を入力して作成される木は以下の通りです。

出力

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] の2つのvectorを用意します。

• Node_Weight[] を各ノードの重みで初期化します。

• vector型の edge_graph を使って木（グラフ）を構築します。

• グローバル変数 square を宣言し、0で初期化します。

• 関数 check(int check_it) は整数を受け取り、それが完全平方数であれば true を返します。

• まず total = sqrt(check_it) を計算します。

• floor(total) != ceil(total) が true であれば total は整数ではない、つまり完全平方数ではないので false を返します。

• それ以外の場合は true を返します。

• 関数 perfect_square(int node, int root) は、ノードとその親（ルート）ノードを受け取り、与えられた木の中で重みが完全平方数であるノードの数を返します。

• check(Node_Weight[node]) が true を返した場合、square をインクリメントします。

• forループを使って edge_graph[node] 内の木を走査します。

• vector内の次のノードに対して 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;
}
// DFSで木を走査し、条件を満たすノードをカウントする関数
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