Smallest vertex in the connected components of all the vertices in given undirect graph | Python 3 program for the above approach ; Stores the parent and size of the set of the ith element ; Function to initialize the ith set ; Function to find set of ith vertex ; Base Case ; Recursive call to find set ; Function to unite the set that includes a and the set that includes b ; If a and b are not from same set ; Function to find the smallest vertex in the connected component of the ith vertex for all i in range [ 1 , N ] ; Loop to initialize the ith set ; Loop to unite all vertices connected by edges into the same set ; Stores the minimum vertex value for ith set ; Loop to iterate over all vertices ; If current vertex does not exist in minVal initialize it with i ; Update the minimum value of the set having the ith vertex ; Loop to print required answer ; Driver Code
maxn = 100 NEW_LINE parent = [ 0 ] * maxn NEW_LINE Size = [ 0 ] * maxn NEW_LINE def make_set ( v ) : NEW_LINE INDENT parent [ v ] = v NEW_LINE Size [ v ] = 1 NEW_LINE DEDENT def find_set ( v ) : NEW_LINE INDENT if ( v == parent [ v ] ) : NEW_LINE INDENT return v NEW_LINE DEDENT parent [ v ] = find_set ( parent [ v ] ) NEW_LINE return parent [ v ] NEW_LINE DEDENT def union_sets ( a , b ) : NEW_LINE INDENT a = find_set ( a ) NEW_LINE b = find_set ( b ) NEW_LINE if ( a != b ) : NEW_LINE INDENT if ( Size [ a ] < Size [ b ] ) : NEW_LINE INDENT a , b = b , a NEW_LINE DEDENT parent [ b ] = a NEW_LINE Size [ a ] += Size [ b ] NEW_LINE DEDENT DEDENT def findMinVertex ( N , edges ) : NEW_LINE INDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT make_set ( i ) NEW_LINE DEDENT for i in range ( len ( edges ) ) : NEW_LINE INDENT union_sets ( edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) NEW_LINE DEDENT minVal = { } NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( find_set ( i ) not in minVal ) : NEW_LINE INDENT minVal [ find_set ( i ) ] = i NEW_LINE DEDENT else : NEW_LINE INDENT minVal [ find_set ( i ) ] = min ( minVal [ find_set ( i ) ] , i ) NEW_LINE DEDENT DEDENT for i in range ( 1 , N + 1 ) : NEW_LINE INDENT print ( minVal [ find_set ( i ) ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 6 NEW_LINE edges = [ [ 1 , 3 ] , [ 2 , 4 ] ] NEW_LINE findMinVertex ( N , edges ) NEW_LINE DEDENT