Dados de 1 a N vértices de un gráfico no cíclico no dirigido con (N-1) aristas. La tarea es asignar valores a estos bordes para que el árbol construido sea un Prime Tree . Prime Tree es un tipo de árbol binario en el que la suma de dos aristas consecutivas del gráfico es un número primo y cada arista también es un número primo. Devuelve el peso de los bordes si la construcción de Prime Tree es posible a partir del gráfico dado; de lo contrario, devuelve -1. Si son posibles múltiples respuestas, imprima cualquiera de ellas.
Ejemplos:
Entrada: N = 5, aristas = [[1, 2], [3, 5], [3, 1], [4, 2]] Salida: 3, 3, 2, 2 Explicación:
Consulte el
diagrama .
Gráfico no dirigido que también es un árbol principal
Entrada: N = 4, aristas = [[1, 2], [4, 2], [2, 3]]
Salida: -1
Enfoque: Este problema se basa en el concepto de un gráfico . Implemente un gráfico con la ayuda de una lista de adyacencia, luego siga los pasos a continuación:
- Si algún vértice tiene más de dos vecinos, entonces no es posible construir Prime Tree , devuelva -1 .
- Designe fuente src a ese vértice que tiene solo un vecino.
- Comience a visitar a los vecinos si no los visitó y asigne 2 y 3 valores a los bordes alternativamente o dos números primos cuya suma también sea un número primo.
- Al momento de sumar valores mantén el registro de vértices con la ayuda de una Tabla Hash.
- Devuelva el valor de los bordes con la ayuda de la tabla Hash.
A continuación se muestra la implementación del enfoque anterior.
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);
}
}
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>
Producción
2 2 3 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)