Count the nodes in the given Tree whose weight is a Perfect Number | C ++ implementation to Count the nodes in the given tree whose weight is a Perfect Number ; Function that returns true if n is perfect ; Variable to store sum of divisors ; Find all divisors and add them ; Check if sum of divisors is equal to n , then n is a perfect number ; Function to perform dfs ; If weight of the current node is a perfect number ; Driver code ; Weights of the node ; Edges of the tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; int ans = 0 ; vector < int > graph [ 100 ] ; vector < int > weight ( 100 ) ; bool isPerfect ( long long int n ) { long long int sum = 1 ; for ( long long int i = 2 ; i * i <= n ; i ++ ) { if ( n % i == 0 ) { if ( i * i != n ) sum = sum + i + n / i ; else sum = sum + i ; } } if ( sum == n && n != 1 ) return true ; return false ; } void dfs ( int node , int parent ) { if ( isPerfect ( weight [ node ] ) ) ans += 1 ; for ( int to : graph [ node ] ) { if ( to == parent ) continue ; dfs ( to , node ) ; } } int main ( ) { weight [ 1 ] = 5 ; weight [ 2 ] = 10 ; weight [ 3 ] = 11 ; weight [ 4 ] = 8 ; weight [ 5 ] = 6 ; graph [ 1 ] . push_back ( 2 ) ; graph [ 2 ] . push_back ( 3 ) ; graph [ 2 ] . push_back ( 4 ) ; graph [ 1 ] . push_back ( 5 ) ; dfs ( 1 , 1 ) ; cout << ans ; return 0 ; }