Number of connected components of a graph ( using Disjoint Set Union ) | Stores the parent of each vertex ; Function to find the topmost parent of vertex a ; If current vertex is the topmost vertex ; Otherwise , set topmost vertex of its parent as its topmost vertex ; Function to connect the component having vertex a with the component having vertex b ; Connect edges ; Function to find unique top most parents ; Traverse all vertices ; Insert all topmost vertices obtained ; Print count of connected components ; Function to print answer ; Setting parent to itself ; Traverse all edges ; Print answer ; Given N ; Given edges ; Function call
parent = [ 0 ] * ( 1000000 ) NEW_LINE def root ( a ) : NEW_LINE INDENT if ( a == parent [ a ] ) : NEW_LINE INDENT return a NEW_LINE DEDENT parent [ a ] = root ( parent [ a ] ) NEW_LINE return parent [ a ] NEW_LINE DEDENT def connect ( a , b ) : NEW_LINE INDENT a = root ( a ) NEW_LINE b = root ( b ) NEW_LINE if ( a != b ) : NEW_LINE INDENT parent [ b ] = a NEW_LINE DEDENT DEDENT def connectedComponents ( n ) : NEW_LINE INDENT s = set ( ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT s . add ( root ( parent [ i ] ) ) NEW_LINE DEDENT print ( len ( s ) ) NEW_LINE DEDENT def printAnswer ( N , edges ) : NEW_LINE INDENT for i in range ( N + 1 ) : NEW_LINE INDENT parent [ i ] = i NEW_LINE DEDENT for i in range ( len ( edges ) ) : NEW_LINE INDENT connect ( edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) NEW_LINE DEDENT connectedComponents ( N ) NEW_LINE DEDENT N = 6 NEW_LINE edges = [ [ 1 , 0 ] , [ 2 , 3 ] , [ 1 , 2 ] , [ 4 , 5 ] ] NEW_LINE printAnswer ( N , edges ) NEW_LINE