Nodes with prime degree in an undirected Graph | C ++ implementation of the approach ; To store Prime Numbers ; Function to find the prime numbers till 10 ^ 5 ; Traverse all multiple of i and make it false ; Function to print the nodes having prime degree ; To store Adjacency List of a Graph ; Make Adjacency List ; To precompute prime numbers till 10 ^ 5 ; Traverse each vertex ; Find size of Adjacency List ; If length of Adj [ i ] is Prime then print it ; Driver code ; Vertices and Edges ; Edges ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int n = 10005 ; vector < bool > Prime ( n + 1 , true ) ; void SieveOfEratosthenes ( ) { int i , j ; Prime [ 0 ] = Prime [ 1 ] = false ; for ( i = 2 ; i * i <= 10005 ; i ++ ) { if ( Prime [ i ] ) { for ( j = 2 * i ; j < 10005 ; j += i ) { Prime [ j ] = false ; } } } } void primeDegreeNodes ( int N , int M , int edges [ ] [ 2 ] ) { vector < int > Adj [ N + 1 ] ; for ( int i = 0 ; i < M ; i ++ ) { int x = edges [ i ] [ 0 ] ; int y = edges [ i ] [ 1 ] ; Adj [ x ] . push_back ( y ) ; Adj [ y ] . push_back ( x ) ; } SieveOfEratosthenes ( ) ; for ( int i = 1 ; i <= N ; i ++ ) { int x = Adj [ i ] . size ( ) ; if ( Prime [ x ] ) cout << i << ' ▁ ' ; } } int main ( ) { int N = 4 , M = 6 ; int edges [ M ] [ 2 ] = { { 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 } , { 3 , 4 } } ; primeDegreeNodes ( N , M , edges ) ; return 0 ; }