Maximum element in connected component of given node for Q queries | Java 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 ] [ 0 ] and arr [ i ] [ 1 ] 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
import java . util . * ; class GFG { static int Find ( int [ ] parent , int a ) { return parent [ a ] = ( parent [ a ] == a ) ? a : ( Find ( parent , parent [ a ] ) ) ; } static void Union ( int [ ] parent , int [ ] rank , 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 ] = Math . max ( maxValue [ a ] , maxValue [ b ] ) ; } static void findMaxValueOfSet ( int [ ] [ ] arr , int [ ] queries , int R , int N , int M ) { int [ ] parent = new int [ R + 1 ] ; int [ ] rank = new int [ R + 1 ] ; int [ ] maxValue = new int [ 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 ] [ 0 ] , arr [ i ] [ 1 ] ) ; } for ( int i = 0 ; i < M ; i ++ ) { int P = Find ( parent , queries [ i ] ) ; System . out . print ( maxValue [ P ] + " ▁ " ) ; } } public static void main ( String [ ] args ) { int R = 5 ; int [ ] [ ] arr = { { 1 , 2 } , { 2 , 3 } , { 4 , 5 } } ; int [ ] queries = { 2 , 4 , 1 , 3 } ; int N = arr . length ; int M = queries . length ; findMaxValueOfSet ( arr , queries , R , N , M ) ; } }