Maximum element in connected component of given node for Q queries | 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
def Find ( parent , a ) : NEW_LINE INDENT if ( parent [ parent [ a ] ] != parent [ a ] ) : NEW_LINE INDENT parent [ a ] = findParent ( parent , parent [ a ] ) NEW_LINE DEDENT return parent [ a ] NEW_LINE DEDENT def Union ( parent , rank , maxValue , a , b ) : NEW_LINE INDENT a = Find ( parent , a ) NEW_LINE b = Find ( parent , b ) NEW_LINE if ( a == b ) : NEW_LINE INDENT return NEW_LINE DEDENT if ( rank [ a ] == rank [ b ] ) : NEW_LINE INDENT rank [ a ] += 1 NEW_LINE DEDENT if ( rank [ a ] < rank [ b ] ) : NEW_LINE INDENT temp = a NEW_LINE a = b NEW_LINE b = temp NEW_LINE DEDENT parent [ b ] = a NEW_LINE maxValue [ a ] = max ( maxValue [ a ] , maxValue [ b ] ) NEW_LINE DEDENT def findMaxValueOfSet ( arr , queries , R , N , M ) : NEW_LINE INDENT parent = [ 1 for i in range ( R + 1 ) ] NEW_LINE rank = [ 0 for i in range ( R + 1 ) ] NEW_LINE maxValue = [ 0 for i in range ( R + 1 ) ] NEW_LINE for i in range ( 1 , R + 1 , 1 ) : NEW_LINE INDENT parent [ i ] = maxValue [ i ] = i NEW_LINE DEDENT for i in range ( N ) : NEW_LINE INDENT Union ( parent , rank , maxValue , arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) NEW_LINE DEDENT for i in range ( M ) : NEW_LINE INDENT P = Find ( parent , queries [ i ] ) NEW_LINE print ( maxValue [ P ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT R = 5 NEW_LINE arr = [ [ 1 , 2 ] , [ 2 , 3 ] , [ 4 , 5 ] ] ; NEW_LINE queries = [ 2 , 4 , 1 , 3 ] NEW_LINE N = len ( arr ) NEW_LINE M = len ( queries ) NEW_LINE findMaxValueOfSet ( arr , queries , R , N , M ) NEW_LINE DEDENT