Largest component size in a graph formed by connecting non | C # 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
using System ; using System . Collections . Generic ; class GFG { static int dfs ( int u , List < int > [ ] adj , int [ ] vis ) { vis [ u ] = 1 ; int componentSize = 1 ; foreach ( int it in adj [ u ] ) { if ( vis [ it ] == 0 ) { componentSize += dfs ( it , adj , vis ) ; } } return componentSize ; } static int maximumComponentSize ( int [ ] a , int n ) { List < int > [ ] adj = new List < int > [ n ] ; for ( int i = 0 ; i < adj . Length ; i ++ ) adj [ i ] = new List < int > ( ) ; 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 } ; Console . Write ( maximumComponentSize ( A , n ) ) ; } }