Largest component size in a graph formed by connecting non |  ; 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
import java . util . * ; class GFG { static int dfs ( int u , Vector < Integer > [ ] adj , int vis [ ] ) { vis [ u ] = 1 ; int componentSize = 1 ; for ( int it : adj [ u ] ) { if ( vis [ it ] == 0 ) { componentSize += dfs ( it , adj , vis ) ; } } return componentSize ; } static int maximumComponentSize ( int a [ ] , int n ) { @ SuppressWarnings ( " unchecked " ) Vector < Integer > [ ] adj = new Vector [ n ] ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { if ( __gcd ( a [ i ] , a [ j ] ) > 1 ) adj [ i ] . add ( j ) ; adj [ j ] . add ( i ) ; } } int answer = 0 ; int [ ] vis = new int [ n ] ; for ( int k = 0 ; k < n ; k ++ ) { vis [ k ] = 0 ; } for ( int i = 0 ; i < n ; i ++ ) { if ( vis [ i ] == 0 ) { answer = Math . max ( answer , dfs ( i , adj , vis ) ) ; } } return answer ; } static int __gcd ( int a , int b ) { return b == 0 ? a : __gcd ( b , a % b ) ; } public static void main ( String [ ] args ) { int n = 8 ; int A [ ] = { 2 , 3 , 6 , 7 , 4 , 12 , 21 , 39 } ; System . out . print ( maximumComponentSize ( A , n ) ) ; } }