Count the number of Prime Cliques in an undirected graph | C # implementation to count the number of Prime Cliques in an undirected graph ; Stores the vertices ; Graph ; Degree of the vertices ; To store the count of prime cliques ; Function to create Sieve to check primes ; False here indicates that it is not prime ; Condition if prime [ p ] is not changed , then it is a prime ; Update all multiples of p , set them to non - prime ; Function to check if the given set of vertices in store array is a clique or not ; Run a loop for all set of edges ; If any edge is missing ; Function to find the count of all the cliques having prime size ; Check if any vertices from i + 1 can be inserted ; Add the vertex to store ; If the graph is not a clique of size k then it cannot be a clique by adding another edge ; Increase the count of prime cliques if the size of current clique is prime ; Check if another edge can be added ; Driver code
using System ; class GFG { static readonly int MAX = 100 ; static int [ ] store = new int [ MAX ] ; static int n ; static int [ , ] graph = new int [ MAX , MAX ] ; static int [ ] d = new int [ MAX ] ; static int ans ; static void SieveOfEratosthenes ( bool [ ] prime , int p_size ) { prime [ 0 ] = false ; prime [ 1 ] = false ; for ( int p = 2 ; p * p <= p_size ; p ++ ) { if ( prime [ p ] ) { for ( int i = p * 2 ; i <= p_size ; i += p ) prime [ i ] = false ; } } } static bool is_clique ( int b ) { for ( int i = 1 ; i < b ; i ++ ) { for ( int j = i + 1 ; j < b ; j ++ ) if ( graph [ store [ i ] , store [ j ] ] == 0 ) return false ; } return true ; } static void primeCliques ( int i , int l , bool [ ] prime ) { for ( int j = i + 1 ; j <= n ; j ++ ) { store [ l ] = j ; if ( is_clique ( l + 1 ) ) { if ( prime [ l ] ) ans ++ ; primeCliques ( j , l + 1 , prime ) ; } } } public static void Main ( String [ ] args ) { int [ , ] edges = { { 1 , 2 } , { 2 , 3 } , { 3 , 1 } , { 4 , 3 } , { 4 , 5 } , { 5 , 3 } } ; int size = edges . GetLength ( 0 ) ; n = 5 ; bool [ ] prime = new bool [ n + 1 ] ; for ( int i = 0 ; i < prime . Length ; i ++ ) prime [ i ] = true ; SieveOfEratosthenes ( prime , n ) ; for ( int i = 0 ; i < size ; i ++ ) { graph [ edges [ i , 0 ] , edges [ i , 1 ] ] = 1 ; graph [ edges [ i , 1 ] , edges [ i , 0 ] ] = 1 ; d [ edges [ i , 0 ] ] ++ ; d [ edges [ i , 1 ] ] ++ ; } ans = 0 ; primeCliques ( 0 , 1 , prime ) ; Console . WriteLine ( ans ) ; } }