Construct a Prime Binary Tree from given non-cyclic graph of N indices
Given 1 to N vertices of a non-cyclic undirected graph with (N-1) edges. The task is to assign values to these edges so that the constructed tree is a Prime Tree. Prime Tree is a type of Binary Tree in which the sum of two consecutive edges of the graph is a prime number and each edge is also a prime number. Return the weight of edges if construction of Prime Tree is possible from given graph otherwise return -1. If multiple answers are possible, print any one of them.
Examples:
Input: N = 5, edges = [[1, 2], [3, 5], [3, 1], [4, 2]]
Output: 3, 3, 2, 2
Explanation: Refer to the diagram.Input: N = 4, edges = [[1, 2], [4, 2], [2, 3]]
Output: -1
Approach: This problem is based on the concept of a graph. Implement a graph with the help of an adjacency list after that follow the below steps:
- If any vertex has more than two neighbours then constructing Prime Tree is not possible, return -1.
- Appoint source src to that vertex that has only one neighbour.
- Start visiting the neighbours if not visited and appoint 2 and 3 values to the edges alternatively or any two primes whose sum is also a prime.
- At the time of adding values maintain the record of vertices with the help of a Hash Table.
- Return the value of edges with the help of the Hash Table.
Below is the implementation of the above approach.
C++
#include <iostream> #include <map> #include <string> #include <vector> using namespace std; // Edge class for Adjacency List class Edge { public : int u, v; Edge( int u, int v) : u(u) , v(v) { } }; // Function to construct a Prime Tree void constructPrimeTree( int N, vector<vector< int > >& edges) { // ArrayList for adjacency list vector<vector<Edge> > graph(N); // Array which stores source and destination vector<string> record(N - 1); // Constructing graph using adjacency List for ( int i = 0; i < edges.size(); i++) { int u = edges[i][0] - 1, v = edges[i][1] - 1; graph[u].push_back(Edge(u, v)); graph[v].push_back(Edge(v, u)); record[i] = to_string(u) + " " + to_string(v); } // Selecting source src int src = 0; for ( int i = 0; i < N; i++) { // If neighour is more than 2 then Prime Tree // construction is not possible if (graph[i].size() > 2) { cout << -1 << endl; return ; } // Appointing src to the vertex which has only 1 // neighbour if (graph[i].size() == 1) src = i; } // Initializing Hash Map which keeps records of source // and destination along with the weight of the edge map<string, int > vertices; int count = 0, weight = 2; // Iterating N-1 times(no. of edges) while (count < N) { auto ed = graph[src]; int i = 0; // Finding unvisited neighbour while (i < ed.size() && vertices.count(record[i])) i++; // Assigning weight to its edge if (i < ed.size()) { int nbr = ed[i].v; vertices[record[i]] = weight; vertices[to_string(nbr) + " " + to_string(src)] = weight; weight = 5 - weight; src = nbr; } count++; } // Printing edge weights for ( auto & r : record) cout << vertices[r] << " " ; cout << endl; } int main() { int N = 5; vector<vector< int > > edges = { { 1, 2 }, { 3, 5 }, { 3, 1 }, { 4, 2 } }; constructPrimeTree(N, edges); return 0; } |
Java
// Java code for the above approach import java.util.*; class GFG { // Edge class for Adjacency List public static class Edge { int u; int v; Edge( int u, int v) { this .u = u; this .v = v; } } // Function to construct a Prime Tree public static void constructPrimeTree( int N, int [][] edges) { // ArrayList for adjacency list @SuppressWarnings ( "unchecked" ) ArrayList<Edge>[] graph = new ArrayList[N]; for ( int i = 0 ; i < N; i++) { graph[i] = new ArrayList<>(); } // Array which stores source // and destination String[] record = new String[N - 1 ]; // Constructing graph using // adjacency List for ( int i = 0 ; i < edges.length; i++) { int u = edges[i][ 0 ]; int v = edges[i][ 1 ]; graph[u - 1 ].add( new Edge(u - 1 , v - 1 )); graph[v - 1 ].add( new Edge(v - 1 , u - 1 )); record[i] = (u - 1 ) + " " + (v - 1 ); } // Selecting source src int src = 0 ; for ( int i = 0 ; i < N; i++) { // If neighour is more than 2 // then Prime Tree construction // is not possible if (graph[i].size() > 2 ) { System.out.println(- 1 ); return ; } // Appointing src to the vertex // which has only 1 neighbour else if (graph[i].size() == 1 ) src = i; } // Initializing Hash Map which // keeps records of source and // destination along with the // weight of the edge Map<String, Integer> vertices = new HashMap<>(); int count = 0 ; int weight = 2 ; // Iterating N-1 times(no. of edges) while (count < N) { List<Edge> ed = graph[src]; int i = 0 ; // Finding unvisited neighbour while (i < ed.size() && vertices.containsKey( src + " " + ed.get(i).v)) i++; // Assigning weight to its edge if (i < ed.size()) { int nbr = ed.get(i).v; vertices.put(src + " " + nbr, weight); vertices.put(nbr + " " + src, weight); weight = 5 - weight; src = nbr; } count++; } // Printing edge weights for ( int i = 0 ; i < record.length; i++) { System.out.print(vertices.get( record[i]) + " " ); } } // Driver Code public static void main(String[] args) { int N = 5 ; int [][] edges = { { 1 , 2 }, { 3 , 5 }, { 3 , 1 }, { 4 , 2 } }; constructPrimeTree(N, edges); } } |
Python3
# Python code for the above approach # Edge class for Adjacency List class Edge: def __init__( self , u, v): self .u = u self .v = v # Function to construct a Prime Tree def constructPrimeTree(N, edges): # ArrayList for adjacency list graph = [[] for _ in range (N)] # Array which stores source and destination record = [ 0 ] * (N - 1 ) # Constructing graph using adjacency List for i in range ( len (edges)): u, v = edges[i] graph[u - 1 ].append(Edge(u - 1 , v - 1 )) graph[v - 1 ].append(Edge(v - 1 , u - 1 )) record[i] = f "{u - 1} {v - 1}" # Selecting source src src = 0 for i in range (N): # If neighour is more than 2 then Prime Tree construction # is not possible if len (graph[i]) > 2 : print ( - 1 ) return # Appointing src to the vertex which has only 1 neighbour elif len (graph[i]) = = 1 : src = i # Initializing Hash Map which keeps records of source and # destination along with the weight of the edge vertices = {} count = 0 weight = 2 # Iterating N-1 times(no. of edges) while count < N: ed = graph[src] i = 0 # Finding unvisited neighbour while i < len (ed) and f "{src} {ed[i].v}" in vertices: i + = 1 # Assigning weight to its edge if i < len (ed): nbr = ed[i].v vertices[f "{src} {nbr}" ] = weight vertices[f "{nbr} {src}" ] = weight weight = 5 - weight src = nbr count + = 1 # Printing edge weights for i in range ( len (record)): print (vertices[record[i]], end = ' ' ) # Driver Code N = 5 edges = [[ 1 , 2 ], [ 3 , 5 ], [ 3 , 1 ], [ 4 , 2 ]] constructPrimeTree(N, edges) # This code is contributed by Potta Lokesh |
C#
using System; using System.Collections.Generic; public class GFG { // Edge class for Adjacency List public class Edge { public int u; public int v; public Edge( int u, int v) { this .u = u; this .v = v; } } // Function to construct a Prime Tree public static void ConstructPrimeTree( int N, int [][] edges) { // ArrayList for adjacency list List<Edge>[] graph = new List<Edge>[ N ]; for ( int i = 0; i < N; i++) { graph[i] = new List<Edge>(); } // Array which stores source and destination string [] record = new string [N - 1]; // Constructing graph using adjacency List for ( int i = 0; i < edges.Length; i++) { int u = edges[i][0]; int v = edges[i][1]; graph[u - 1].Add( new Edge(u - 1, v - 1)); graph[v - 1].Add( new Edge(v - 1, u - 1)); record[i] = (u - 1) + " " + (v - 1); } // Selecting source src int src = 0; for ( int i = 0; i < N; i++) { // If neighbour is more than 2 then Prime Tree // construction is not possible if (graph[i].Count > 2) { Console.WriteLine( "-1" ); return ; } // Appointing src to the vertex which has only 1 // neighbour else if (graph[i].Count == 1) { src = i; } } // Initializing Hash Map which keeps records of // source and destination along with the weight of // the edge Dictionary< string , int > vertices = new Dictionary< string , int >(); int count = 0; int weight = 2; // Iterating N-1 times(no. of edges) while (count < N) { List<Edge> ed = graph[src]; int i = 0; // Finding unvisited neighbour while (i < ed.Count && vertices.ContainsKey(src + " " + ed[i].v)) { i++; } // Assigning weight to its edge if (i < ed.Count) { int nbr = ed[i].v; vertices[src + " " + nbr] = weight; vertices[nbr + " " + src] = weight; weight = 5 - weight; src = nbr; } count++; } // Printing edge weights for ( int i = 0; i < record.Length; i++) { Console.Write(vertices[record[i]] + " " ); } } // Driver Code public static void Main( string [] args) { int N = 5; int [][] edges = { new int [] { 1, 2 }, new int [] { 3, 5 }, new int [] { 3, 1 }, new int [] { 4, 2 } }; ConstructPrimeTree(N, edges); } } |
Javascript
<script> // Javascript code for the above approach // Edge class for Adjacency List class Edge { constructor(u, v) { this .u = u; this .v = v; } } // Function to construct a Prime Tree function constructPrimeTree(N, edges) { // ArrayList for adjacency list let graph = new Array(N); for (let i = 0; i < N; i++) { graph[i] = [] } // Array which stores source // and destination let record = new Array(N - 1); // Constructing graph using // adjacency List for (let i = 0; i < edges.length; i++) { let u = edges[i][0]; let v = edges[i][1]; graph[u - 1].push( new Edge(u - 1, v - 1)); graph[v - 1].push( new Edge(v - 1, u - 1)); record[i] = (u - 1) + " " + (v - 1); } // Selecting source src let src = 0; for (let i = 0; i < N; i++) { // If neighour is more than 2 // then Prime Tree construction // is not possible if (graph[i].length > 2) { document.write(-1); return ; } // Appointing src to the vertex // which has only 1 neighbour else if (graph[i].length == 1) src = i; } // Initializing Hash Map which // keeps records of source and // destination along with the // weight of the edge let vertices = new Map(); let count = 0; let weight = 2; // Iterating N-1 times(no. of edges) while (count < N) { let ed = graph[src]; let i = 0; // Finding unvisited neighbour while (i < ed.length && vertices.has(src + " " + ed[i].v)) i++; // Assigning weight to its edge if (i < ed.length) { let nbr = ed[i].v; vertices.set(src + " " + nbr, weight); vertices.set(nbr + " " + src, weight); weight = 5 - weight; src = nbr; } count++; } // Printing edge weights for (let i = 0; i < record.length; i++) { document.write(vertices.get(record[i]) + " " ); } } // Driver Code let N = 5; let edges = [[1, 2], [3, 5], [3, 1], [4, 2]]; constructPrimeTree(N, edges); // This code is contributed by saurabh_jaiswal. </script> |
2 2 3 3
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us