Given an undirected graph with N vertices and M edges, the task is to print all the nodes of the given graph whose degree is a Prime Number.
Examples:
Input: N = 4, arr[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }
Output: 1 2 3 4
Explanation:
Below is the graph for the above information:
The degree of the node as per above graph is:
Node -> Degree
1 -> 3
2 -> 3
3 -> 3
4 -> 3
Hence, the nodes with prime degree are 1 2 3 4
Input: N = 5, arr[][] = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 2, 5 } }
Output: 1
Approach:
- Use Sieve of Eratosthenes to calculate the prime numbers up to 105.
- For each vertex, the degree can be calculated by the length of the Adjacency List of the given graph at the corresponding vertex.
- Print those vertices of the given graph whose degree is a Prime Number.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;int n = 10005;// To store Prime Numbersvector<bool> Prime(n + 1, true);// Function to find the prime numbers// till 10^5void SieveOfEratosthenes(){ int i, j; Prime[0] = Prime[1] = false; for (i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for (j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreevoid primeDegreeNodes(int N, int M, int edges[][2]){ // To store Adjacency List of // a Graph vector<int> Adj[N + 1]; // Make Adjacency List 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); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for (int i = 1; i <= N; i++) { // Find size of Adjacency List int x = Adj[i].size(); // If length of Adj[i] is Prime // then print it if (Prime[x]) cout << i << ' '; }}// Driver codeint main(){ // Vertices and Edges int N = 4, M = 6; // Edges int edges[M][2] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; // Function Call primeDegreeNodes(N, M, edges); return 0;} |
Java
// Java implementation of the approachimport java.util.*;class GFG{static int n = 10005;// To store Prime Numbersstatic boolean []Prime = new boolean[n + 1];// Function to find the prime numbers// till 10^5static void SieveOfEratosthenes(){ int i, j; Prime[0] = Prime[1] = false; for (i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for (j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreestatic void primeDegreeNodes(int N, int M, int edges[][]){ // To store Adjacency List of // a Graph Vector<Integer> []Adj = new Vector[N + 1]; for(int i = 0; i < Adj.length; i++) Adj[i] = new Vector<Integer>(); // Make Adjacency List for (int i = 0; i < M; i++) { int x = edges[i][0]; int y = edges[i][1]; Adj[x].add(y); Adj[y].add(x); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for (int i = 1; i <= N; i++) { // Find size of Adjacency List int x = Adj[i].size(); // If length of Adj[i] is Prime // then print it if (Prime[x]) System.out.print(i + " "); }}// Driver codepublic static void main(String[] args){ // Vertices and Edges int N = 4, M = 6; // Edges int edges[][] = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; Arrays.fill(Prime, true); // Function Call primeDegreeNodes(N, M, edges);}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 implementation of # the above approachn = 10005; # To store Prime NumbersPrime = [True for i in range(n + 1)] # Function to find # the prime numbers # till 10^5def SieveOfEratosthenes(): i = 2 Prime[0] = Prime[1] = False; while i * i <= 10005: # Traverse all multiple # of i and make it false if (Prime[i]): for j in range(2 * i, 10005): Prime[j] = False i += 1 # Function to print the # nodes having prime degreedef primeDegreeNodes(N, M, edges): # To store Adjacency # List of a Graph Adj = [[] for i in range(N + 1)]; # Make Adjacency List for i in range(M): x = edges[i][0]; y = edges[i][1]; Adj[x].append(y); Adj[y].append(x); # To precompute prime # numbers till 10^5 SieveOfEratosthenes(); # Traverse each vertex for i in range(N + 1): # Find size of Adjacency List x = len(Adj[i]); # If length of Adj[i] is Prime # then print it if (Prime[x]): print(i, end = ' ') # Driver codeif __name__ == "__main__": # Vertices and Edges N = 4 M = 6 # Edges edges = [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]; # Function Call primeDegreeNodes(N, M, edges);# This code is contributed by rutvik_56 |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG{static int n = 10005;// To store Prime Numbersstatic bool []Prime = new bool[n + 1];// Function to find the prime numbers// till 10^5static void SieveOfEratosthenes(){ int i, j; Prime[0] = Prime[1] = false; for(i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for(j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreestatic void primeDegreeNodes(int N, int M, int [,]edges){ // To store Adjacency List of // a Graph List<int> []Adj = new List<int>[N + 1]; for(int i = 0; i < Adj.Length; i++) Adj[i] = new List<int>(); // Make Adjacency List for(int i = 0; i < M; i++) { int x = edges[i, 0]; int y = edges[i, 1]; Adj[x].Add(y); Adj[y].Add(x); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for(int i = 1; i <= N; i++) { // Find size of Adjacency List int x = Adj[i].Count; // If length of Adj[i] is Prime // then print it if (Prime[x]) Console.Write(i + " "); }}// Driver codepublic static void Main(String[] args){ // Vertices and Edges int N = 4, M = 6; // Edges int [,]edges = { { 1, 2 }, { 1, 3 }, { 1, 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 } }; for(int i = 0; i < Prime.Length; i++) Prime[i] = true; // Function Call primeDegreeNodes(N, M, edges);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// JavaScript implementation of the approachlet n = 10005;// To store Prime Numberslet Prime = new Array(n + 1).fill(true);// Function to find the prime numbers// till 10^5function SieveOfEratosthenes(){ let i, j; Prime[0] = Prime[1] = false; for (i = 2; i * i <= 10005; i++) { // Traverse all multiple of i // and make it false if (Prime[i]) { for (j = 2 * i; j < 10005; j += i) { Prime[j] = false; } } }}// Function to print the nodes having// prime degreefunction primeDegreeNodes(N, M, edges){ // To store Adjacency List of // a Graph let Adj = new Array(); for(let i = 0; i < N + 1; i++){ Adj.push(new Array()) } // Make Adjacency List for (let i = 0; i < M; i++) { let x = edges[i][0]; let y = edges[i][1]; Adj[x].push(y); Adj[y].push(x); } // To precompute prime numbers // till 10^5 SieveOfEratosthenes(); // Traverse each vertex for (let i = 1; i <= N; i++) { // Find size of Adjacency List let x = Adj[i].length; // If length of Adj[i] is Prime // then print it if (Prime[x]) document.write(i + ' '); }}// Driver code// Vertices and Edgeslet N = 4, M = 6; // Edgeslet edges = [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ];// Function CallprimeDegreeNodes(N, M, edges);// This code is contributed by gfgking</script> |
Output:
1 2 3 4
Time Complexity: O(N + M), where N is the number of vertices and M is the number of edges.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
