Count the nodes of a tree whose weighted string does not contain any duplicate characters | C ++ implementation of the approach ; Function that returns true if the string contains unique characters ; Function to perform dfs ; If weighted string of the current node contains unique characters ; Driver code ; Weights of the nodes ; Edges of the tree
#include <bits/stdc++.h> NEW_LINE using namespace std ; int cnt = 0 ; vector < int > graph [ 100 ] ; vector < string > weight ( 100 ) ; bool uniqueChars ( string x ) { map < char , int > mp ; int n = x . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) mp [ x [ i ] ] ++ ; if ( mp . size ( ) == x . size ( ) ) return true ; else return false ; } void dfs ( int node , int parent ) { if ( uniqueChars ( weight [ node ] ) ) cnt += 1 ; for ( int to : graph [ node ] ) { if ( to == parent ) continue ; dfs ( to , node ) ; } } int main ( ) { weight [ 1 ] = " abc " ; weight [ 2 ] = " aba " ; weight [ 3 ] = " bcb " ; weight [ 4 ] = " moh " ; weight [ 5 ] = " aa " ; graph [ 1 ] . push_back ( 2 ) ; graph [ 2 ] . push_back ( 3 ) ; graph [ 2 ] . push_back ( 4 ) ; graph [ 1 ] . push_back ( 5 ) ; dfs ( 1 , 1 ) ; cout << cnt ; return 0 ; }