Dado un gráfico conectado no dirigido en forma de árbol que consta de N Nodes y (N – 1) aristas, la tarea de cada arista es contar el número de veces que aparece en todos los caminos posibles del árbol.
Ejemplos:
Aporte:
Salida: 3 4 3
Explicación:
Todos los caminos posibles de un árbol dado son {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) )}
Edge 1 ocurre en las rutas {(1, 2), (1, 3), (1, 4)}. Por lo tanto, la frecuencia del borde es 3. El
borde 2 ocurre en los caminos {(1, 3), (1, 4), (2, 3), (2, 4)}. Por lo tanto, la frecuencia del borde es 4. El
borde 3 ocurre en los caminos {(1, 4), (2, 4), (3, 4)}. Por lo tanto, la frecuencia del borde es 3.
Aporte:
Salida: 4 6 4 4
Explicación:
El borde 1 ocurre en las rutas {(1, 2), (1, 3), (1, 4), (1, 5)}. Por lo tanto, la frecuencia del borde es 4 El
borde 2 ocurre en los caminos {(1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5 )}. Por lo tanto, la frecuencia del borde es 6 El
borde 3 ocurre en los caminos {(1, 4), (2, 4), (3, 4), (4, 5)}. Por lo tanto, la frecuencia del borde es 4 El
borde 4 ocurre en los caminos {(1, 5), (2, 5), (3, 5), (4, 5)}. Por lo tanto, la frecuencia del borde es 4
Enfoque ingenuo: el enfoque más simple es generar todas las rutas posibles desde cada Node del gráfico dado y almacenar el recuento de bordes que ocurren en estas rutas mediante un HashMap . Finalmente, imprima las frecuencias de cada borde.
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: Para optimizar el enfoque anterior, es necesario hacer la siguiente observación:
El borde de color verde aparecerá en todos los caminos que conectan cualquier vértice del subárbol de su izquierda con cualquier vértice del subárbol de su derecha.
Por lo tanto, el número de caminos en los que ocurre el borde = Producto del recuento de Nodes en los dos subárboles = 5 * 3 = 15.
Siga los pasos a continuación para resolver el problema:
- Rootee el árbol en cualquier vértice aleatorio, digamos 1.
- Realice DFS en la raíz. Usando DFS, calcule el tamaño del subárbol conectado a los bordes.
- La frecuencia de cada borde conectado al subárbol es (tamaño del subárbol) * (N – tamaño del subárbol) .
- Almacene el valor calculado anteriormente para cada Node en un HashMap . Finalmente, después de completar el recorrido del árbol, recorra el HashMap para imprimir el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Number of nodes
int N;
// Structure of a Node
struct Node {
int node;
int edgeLabel;
};
// Adjacency List to
// represent the Tree
vector<Node> adj[100005];
// Stores the frequencies
// of every edge
vector<int> freq;
// Function to perform DFS
int dfs(int u = 1, int p = 1)
{
// Add the current node to
// size of subtree rooted at u
int sz = 1;
// Iterate over its children
for (auto a : adj[u]) {
// Check if child is not parent
if (a.node != p) {
// Get the subtree size
// for the child
int val = dfs(a.node, u);
// Set the frequency
// of the current edge
freq[a.edgeLabel]
= val * (N - val);
// Add the subtree size
// to itself
sz += val;
}
}
// Return the subtree size
return sz;
}
// Function to add edge between nodes
void addEdge(int u, int v, int label)
{
adj[u].push_back({ v, label });
adj[v].push_back({ u, label });
}
// Function to print the frequencies
// of each edge in all possible paths
void printFrequencies()
{
// Stores the frequency
// of all the edges
freq = vector<int>(N);
// Perform DFS
dfs();
for (int i = 1; i < N; i++) {
cout << freq[i] << " ";
}
}
// Driver Code
int main()
{
N = 4;
addEdge(1, 2, 1);
addEdge(2, 3, 2);
addEdge(3, 4, 3);
printFrequencies();
return 0;
}
Java
// Java Program to implement
// the above approach
import java.util.*;
class GFG{
// Number of nodes
static int N;
// Structure of a Node
static class Node
{
int node;
int edgeLabel;
public Node(int node, int edgeLabel)
{
super();
this.node = node;
this.edgeLabel = edgeLabel;
}
};
// Adjacency List to
// represent the Tree
static Vector<Node> []adj = new Vector[100005];
// Stores the frequencies
// of every edge
static int []freq;
// Function to perform DFS
static int dfs(int u , int p)
{
// Add the current node to
// size of subtree rooted at u
int sz = 1;
// Iterate over its children
for (Node a : adj[u])
{
// Check if child is not parent
if (a.node != p)
{
// Get the subtree size
// for the child
int val = dfs(a.node, u);
// Set the frequency
// of the current edge
freq[a.edgeLabel] = val * (N - val);
// Add the subtree size
// to itself
sz += val;
}
}
// Return the subtree size
return sz;
}
// Function to add edge between nodes
static void addEdge(int u, int v, int label)
{
adj[u].add(new Node( v, label ));
adj[v].add(new Node( u, label));
}
// Function to print the frequencies
// of each edge in all possible paths
static void printFrequencies()
{
// Stores the frequency
// of all the edges
freq = new int[N];
// Perform DFS
dfs(1, 1);
for (int i = 1; i < N; i++)
{
System.out.print(freq[i] + " ");
}
}
// Driver Code
public static void main(String[] args)
{
N = 4;
for (int i = 0; i < adj.length; i++)
adj[i] = new Vector<Node>();
addEdge(1, 2, 1);
addEdge(2, 3, 2);
addEdge(3, 4, 3);
printFrequencies();
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement # the above approach # Number of nodes N = 4 # Structure of a Node class Node: def __init__(self, v, label): self.node = v self.edgeLabel = label # Adjacency list to # represent the Tree adj = [] for i in range(100005): adj.append([]) # Stores the frequencies # of each edge freq = [0] * N # Function to perform DFS def dfs(u = 1, p = 1): global N # Add the current node to # size of subtree rooted at u sz = 1 # Iterate over its children for a in adj[u]: # Check if child is not parent if a.node != p: # Get the subtree size # for the child val = dfs(a.node, u) # Set the frequency # of the current edge freq[a.edgeLabel] = val * (N - val) # Add the subtree size # to itself sz += val # Return the subtree size return sz # Function to add edge between nodes def addEdge(u, v, label): adj[u].append(Node(v, label)) adj[v].append(Node(u, label)) # Function to print the frequencies # of each edge in all possible paths def printFrequencies(): # Stores the frequency # of all the edges global N # Perform DFS dfs() for i in range(1, N): print(freq[i], end = " ") # Driver code N = 4 addEdge(1, 2, 1) addEdge(2, 3, 2) addEdge(3, 4, 3) printFrequencies() # This code is contributed by Stuti Pathak
C#
// C# Program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Number of nodes
static int N;
// Structure of a Node
public class Node
{
public int node;
public int edgeLabel;
public Node(int node,
int edgeLabel)
{
this.node = node;
this.edgeLabel = edgeLabel;
}
};
// Adjacency List to
// represent the Tree
static List<Node> []adj =
new List<Node>[100005];
// Stores the frequencies
// of every edge
static int []freq;
// Function to perform DFS
static int dfs(int u, int p)
{
// Add the current node to
// size of subtree rooted at u
int sz = 1;
// Iterate over its children
foreach (Node a in adj[u])
{
// Check if child is not parent
if (a.node != p)
{
// Get the subtree size
// for the child
int val = dfs(a.node, u);
// Set the frequency
// of the current edge
freq[a.edgeLabel] = val * (N - val);
// Add the subtree size
// to itself
sz += val;
}
}
// Return the subtree size
return sz;
}
// Function to add edge between nodes
static void addEdge(int u, int v,
int label)
{
adj[u].Add(new Node(v, label));
adj[v].Add(new Node(u, label));
}
// Function to print the frequencies
// of each edge in all possible paths
static void printFrequencies()
{
// Stores the frequency
// of all the edges
freq = new int[N];
// Perform DFS
dfs(1, 1);
for (int i = 1; i < N; i++)
{
Console.Write(freq[i] + " ");
}
}
// Driver Code
public static void Main(String[] args)
{
N = 4;
for (int i = 0; i < adj.Length; i++)
adj[i] = new List<Node>();
addEdge(1, 2, 1);
addEdge(2, 3, 2);
addEdge(3, 4, 3);
printFrequencies();
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// Javascript Program to implement the above approach
// Number of nodes
let N;
// Structure of a Node
class Node
{
constructor(node, edgeLabel) {
this.node = node;
this.edgeLabel = edgeLabel;
}
}
// Adjacency List to
// represent the Tree
let adj = new Array(100005);
// Stores the frequencies
// of every edge
let freq;
// Function to perform DFS
function dfs(u, p)
{
// Add the current node to
// size of subtree rooted at u
let sz = 1;
// Iterate over its children
for (let a = 0; a < adj[u].length; a++)
{
// Check if child is not parent
if (adj[u][a].node != p)
{
// Get the subtree size
// for the child
let val = dfs(adj[u][a].node, u);
// Set the frequency
// of the current edge
freq[adj[u][a].edgeLabel] = val * (N - val);
// Add the subtree size
// to itself
sz += val;
}
}
// Return the subtree size
return sz;
}
// Function to add edge between nodes
function addEdge(u, v, label)
{
adj[u].push(new Node( v, label ));
adj[v].push(new Node( u, label));
}
// Function to print the frequencies
// of each edge in all possible paths
function printFrequencies()
{
// Stores the frequency
// of all the edges
freq = new Array(N);
// Perform DFS
dfs(1, 1);
for (let i = 1; i < N; i++)
{
document.write(freq[i] + " ");
}
}
N = 4;
for (let i = 0; i < adj.length; i++)
adj[i] = [];
addEdge(1, 2, 1);
addEdge(2, 3, 2);
addEdge(3, 4, 3);
printFrequencies();
</script>
3 4 3
Complejidad temporal: O(N)
Espacio auxiliar : O(N)