Largest component size in a graph formed by connecting non | Javascript program to implement the above approach ; Mark this node as visited ; Apply dfs and add nodes belonging to this component ; Create graph and store in adjacency list form ; Iterate over all pair of nodes ; If not co - prime ; Build undirected graph ; Visited array for dfs ; Utility gcd ; Driver Code
function dfs ( u , adj , vis ) { vis [ u ] = 1 ; let componentSize = 1 ; for ( let it in adj [ u ] ) { if ( vis [ it ] == 0 ) { componentSize += dfs ( it , adj , vis ) ; } } return componentSize ; } function maximumComponentSize ( a , n ) { let adj = new Array ( n ) ; for ( var i = 0 ; i < adj . length ; i ++ ) { adj [ i ] = new Array ( 2 ) ; } for ( var i = 0 ; i < adj . length ; i ++ ) { for ( var j = 0 ; j < adj . length ; j ++ ) { adj [ i ] [ j ] = 0 ; } } for ( let i = 0 ; i < n ; i ++ ) { for ( let j = i + 1 ; j < n ; j ++ ) { if ( __gcd ( a [ i ] , a [ j ] ) > 1 ) adj [ i ] . push ( j ) ; adj [ j ] . push ( i ) ; } } let answer = 0 ; let vis = Array . from ( { length : n } , ( _ , i ) => 0 ) ; for ( let k = 0 ; k < n ; k ++ ) { vis [ k ] = 0 ; } for ( let i = 0 ; i < n ; i ++ ) { if ( vis [ i ] == 0 ) { answer = Math . max ( answer , dfs ( i , adj , vis ) ) ; } } return answer ; } function __gcd ( a , b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } let n = 8 ; let A = [ 2 , 3 , 6 , 7 , 4 , 12 , 21 , 39 ] ; document . write ( maximumComponentSize ( A , n ) ) ;