C++에서 가중치가 완전제곱인 노드 수를 세십시오.

노드의 가중치가 있는 이진 트리가 제공됩니다. 목표는 숫자가 완전제곱이 되도록 가중치를 갖는 노드의 수를 찾는 것입니다. 가중치가 36이면 62이므로 이 노드가 계산됩니다.

예를 들어

입력

값을 입력한 후 생성될 트리는 다음과 같습니다. -

출력

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를 적용하여 트리를 탐색하고 노드의 가중치가 완전제곱인지 확인합니다. 이를 위해 두 벡터 Node_Weight(100) 및 edge_graph[100]를 사용합니다.

• 노드의 가중치로 Node_Weight[]를 초기화합니다.

• 벡터 edge_graph를 사용하여 나무를 만듭니다.

• 전역 변수 square를 가져와 0으로 초기화합니다.

• check(int check_it) 함수는 정수를 취하여 check_it이 완전제곱수이면 true를 반환합니다.

• 합계 =sqrt(check_it)

• 이제 if(floor(total) !=ceil(total))이 true를 반환하면 total이 완전제곱수가 아닌 경우 false를 반환합니다.

• 그렇지 않으면 true를 반환합니다.

• Perfect_square(int node, int root) 함수는 트리의 노드와 루트 노드를 취하여 주어진 트리에서 가중치가 완전제곱인 노드의 수를 반환합니다.

• if(check(Node_Weight[node]))가 true를 반환하면 제곱을 증가시킵니다.

• for 루프를 사용하여 벡터 edge_graph[노드]에서 트리를 탐색합니다.

• 벡터의 다음 노드에 대해 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