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
var parent = Array ( 1000000 ) ; function root ( a ) { if ( a == parent [ a ] ) { return a ; } return parent [ a ] = root ( parent [ a ] ) ; } function connect ( a , b ) { a = root ( a ) ; b = root ( b ) ; if ( a != b ) { parent [ b ] = a ; } } function connectedComponents ( n ) { var s = new Set ( ) ; for ( var i = 0 ; i < n ; i ++ ) { s . add ( parent [ i ] ) ; } document . write ( s . size + " " ) ; } function printAnswer ( N , edges ) { for ( var i = 0 ; i <= N ; i ++ ) { parent [ i ] = i ; } for ( var i = 0 ; i < edges . length ; i ++ ) { connect ( edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) ; } connectedComponents ( N ) ; } var N = 8 ; var edges = [ [ 1 , 0 ] , [ 0 , 2 ] , [ 5 , 3 ] , [ 3 , 4 ] , [ 6 , 7 ] ] ; printAnswer ( N , edges ) ;