Maximum element in connected component of given node for Q queries | 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 ; If the rank are the same ; Update the maximum value ; Function to find the maximum element of the set which belongs to the element queries [ i ] ; Stores the parent elements of the sets ; Stores the rank of the sets ; Stores the maxValue of the sets ; Update parent [ i ] and maxValue [ i ] to i ; Add arr [ i ] . first and arr [ i ] . second elements to the same set ; Find the parent element of the element queries [ i ] ; Print the maximum value of the set which belongs to the element P ; 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 , vector < int > & maxValue , int a , int b ) { a = Find ( parent , a ) ; b = Find ( parent , b ) ; if ( a == b ) return ; if ( rank [ a ] == rank [ b ] ) { rank [ a ] ++ ; } if ( rank [ a ] < rank [ b ] ) { int temp = a ; a = b ; b = temp ; } parent [ b ] = a ; maxValue [ a ] = max ( maxValue [ a ] , maxValue [ b ] ) ; } void findMaxValueOfSet ( vector < pair < int , int > > & arr , vector < int > & queries , int R , int N , int M ) { vector < int > parent ( R + 1 ) ; vector < int > rank ( R + 1 , 0 ) ; vector < int > maxValue ( R + 1 ) ; for ( int i = 1 ; i < R + 1 ; i ++ ) { parent [ i ] = maxValue [ i ] = i ; } for ( int i = 0 ; i < N ; i ++ ) { Union ( parent , rank , maxValue , arr [ i ] . first , arr [ i ] . second ) ; } for ( int i = 0 ; i < M ; i ++ ) { int P = Find ( parent , queries [ i ] ) ; cout << maxValue [ P ] << " ▁ " ; } } int main ( ) { int R = 5 ; vector < pair < int , int > > arr { { 1 , 2 } , { 2 , 3 } , { 4 , 5 } } ; vector < int > queries { 2 , 4 , 1 , 3 } ; int N = arr . size ( ) ; int M = queries . size ( ) ; findMaxValueOfSet ( arr , queries , R , N , M ) ; return 0 ; }