Count of distinct groups of strings formed after performing equivalent operation | C ++ program for the above approach ; Function to perform the find operation to find the parent of a disjoint set ; Function to perform union operation of disjoint set union ; Find the parent of node a and b ; Update the rank ; Function to find the number of distinct strings after performing the given operations ; Stores the parent elements of the sets ; Stores the rank of the sets ; Update parent [ i ] to i ; Stores the total characters traversed through the strings ; Stores the current characters traversed through a string ; Update current [ i ] to false ; Update current [ ch - ' a ' ] to true ; Check if current [ j ] is true ; Update total [ j ] to true ; Add arr [ i ] [ 0 ] - ' a ' and j elements to same set ; Stores the count of distinct strings ; Check total [ i ] is true and parent of i is i only ; Increment the value of distCount by 1 ; Print the value of distCount ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Find ( vector < int > & parent , int a ) { return parent [ a ] = ( parent [ a ] == a ? a : Find ( parent , parent [ a ] ) ) ; } void Union ( vector < int > & parent , vector < int > & rank , int a , int b ) { a = Find ( parent , a ) ; b = Find ( parent , b ) ; if ( rank [ a ] == rank [ b ] ) rank [ a ] ++ ; if ( rank [ a ] > rank [ b ] ) parent [ b ] = a ; else parent [ a ] = b ; } void numOfDistinctStrings ( string arr [ ] , int N ) { vector < int > parent ( 27 ) ; vector < int > rank ( 27 , 0 ) ; for ( int j = 0 ; j < 27 ; j ++ ) { parent [ j ] = j ; } vector < bool > total ( 26 , false ) ; vector < bool > current ( 26 , false ) ; for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < 26 ; j ++ ) { current [ j ] = false ; } for ( char ch : arr [ i ] ) { current [ ch - ' a ' ] = true ; } for ( int j = 0 ; j < 26 ; j ++ ) { if ( current [ j ] ) { total [ j ] = true ; Union ( parent , rank , arr [ i ] [ 0 ] - ' a ' , j ) ; } } } int distCount = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( total [ i ] && Find ( parent , i ) == i ) { distCount ++ ; } } cout << distCount << endl ; } int main ( ) { string arr [ ] = { " a " , " ab " , " b " , " d " } ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; numOfDistinctStrings ( arr , N ) ; return 0 ; }