C++で重みが完全な正方形であるノードを数えます

例

入力

値を入力した後に作成されるツリーを以下に示します-

出力

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

説明

ツリーノードと各ノードに関連付けられた重みが与えられます。次に、ノードの桁が完全な平方であるかどうかを確認します。

入力

値を入力した後に作成されるツリーを以下に示します-

出力

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

説明

we are given with the tree nodes and the weights associated with each
node. Now we check whether the digits of nodes are perfect squares or not.

以下のプログラムで使用されるアプローチは次のとおりです −

このアプローチでは、ツリーのグラフにDFSを適用してツリーをトラバースし、ノードの重みが完全な正方形であるかどうかを確認します。この目的のために、2つのベクトルNode_Weight（100）とedge_graph[100]を取ります。

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

• ベクトルedge_graphを使用してツリーを作成します。

• グローバル変数の正方形を取り、0で初期化します。

• 関数check（int check_it）は整数を取り、check_itが完全な正方形の場合はtrueを返します。

• 合計を取る=sqrt（check_it）

• ここで、（floor（total）！=ceil（total））がtrueを返す場合、totalは完全な正方形ではないため、falseを返します。

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

• 関数perfect_square（int node、int root）は、ツリーのノードとルートノードを取得し、重みが完全な平方である、指定されたツリー内のノードの数を返します。

• if（check（Node_Weight [node]））がtrueを返す場合は、正方形をインクリメントします。

• forループを使用してベクトルedge_graph[node]のツリーをトラバースします。

• ベクトル内の次のノードに対して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(){
   //weight of the nodes
   Node_Weight[2] = 121;
   Node_Weight[1] = 81;
   Node_Weight[4] = 37;
   Node_Weight[3] = 25;
   Node_Weight[8] = 100;
   Node_Weight[9] = 701;
   //create graph edge
   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