Count the nodes of the tree which make a pangram when concatenated with the sub | C ++ implementation of the approach ; Function that returns if the string x is a pangram ; Function to return the count of nodes which make pangram with the sub - tree nodes ; Function to perform dfs and update the nodes such that weight [ i ] will store the weight [ i ] concatenated with the weights of all the nodes in the sub - tree ; Driver code ; Weights of the nodes ; Edges of the tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > graph [ 100 ] ; vector < string > weight ( 100 ) ; bool Pangram ( string x ) { map < char , int > mp ; int n = x . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) mp [ x [ i ] ] ++ ; if ( mp . size ( ) == 26 ) return true ; else return false ; } int countTotalPangram ( int n ) { int cnt = 0 ; for ( int i = 1 ; i <= n ; i ++ ) if ( Pangram ( weight [ i ] ) ) cnt ++ ; return cnt ; } void dfs ( int node , int parent ) { for ( int to : graph [ node ] ) { if ( to == parent ) continue ; dfs ( to , node ) ; weight [ node ] += weight [ to ] ; } } int main ( ) { int n = 6 ; weight [ 1 ] = " abcde " ; weight [ 2 ] = " fghijkl " ; weight [ 3 ] = " abcdefg " ; weight [ 4 ] = " mnopqr " ; weight [ 5 ] = " stuvwxy " ; weight [ 6 ] = " zabcdef " ; graph [ 1 ] . push_back ( 2 ) ; graph [ 2 ] . push_back ( 3 ) ; graph [ 2 ] . push_back ( 4 ) ; graph [ 1 ] . push_back ( 5 ) ; graph [ 5 ] . push_back ( 6 ) ; dfs ( 1 , 1 ) ; cout << countTotalPangram ( n ) ; return 0 ; }