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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 100 ; int store [ MAX ] , n ; int graph [ MAX ] [ MAX ] ; int d [ MAX ] ; int ans ; 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 ; } } } 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 ; } 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 ) ; } } } int main ( ) { int edges [ ] [ 2 ] = { { 1 , 2 } , { 2 , 3 } , { 3 , 1 } , { 4 , 3 } , { 4 , 5 } , { 5 , 3 } } ; int size = sizeof ( edges ) / sizeof ( edges [ 0 ] ) ; n = 5 ; bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; SieveOfEratosthenes ( prime , n + 1 ) ; 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 ) ; cout << ans << " STRNEWLINE " ; return 0 ; }