Dado un árbol , la tarea es encontrar el Node más lejano de cada Node a otro Node en el árbol dado.
Ejemplos
Aporte:
Salida: 2 3 3 3 4 4 4
Explicación:
Distancia máxima desde el Node 1 : 2 (los Nodes {5, 6, 7} están a una distancia 2)
Distancia máxima desde el Node 2 : 3 (los Nodes {6, 7} están a una distancia 3)
Distancia máxima desde el Node 3: 3 (los Nodes {5, 6, 7} están a una distancia 3)
Distancia máxima desde el Node 4: 3 (el Node {5} está a una distancia 3)
Distancia máxima desde el Node 5: 4 (Los Nodes {6, 7} están a una distancia 4)
Distancia máxima desde el Node 6: 4 (Node {5} está a una distancia 4)
Distancia máxima desde el Node 7: 4 (Node {5} está a una distancia 4)Aporte:
Salida : 3 2 3 3 2 3
Acercarse:
Siga los pasos a continuación para resolver el problema:
- Calcule la altura de cada Node del árbol (suponiendo que los Nodes de hoja estén en la altura 1) usando DFS
- Esto da la distancia máxima de un Node a todos los Nodes presentes en su Subárbol. Guarde estas alturas.
- Ahora, realice DFS para calcular la distancia máxima de un Node de todos sus ancestros. Guarde estas distancias.
- Para cada Node, imprima el máximo de las dos distancias calculadas.
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;
#define maxN 100001
// Adjacency List to store the graph
vector<int> adj[maxN];
// Stores the height of each node
int height[maxN];
// Stores the maximum distance of a
// node from its ancestors
int dist[maxN];
// Function to add edge between
// two vertices
void addEdge(int u, int v)
{
// Insert edge from u to v
adj[u].push_back(v);
// Insert edge from v to u
adj[v].push_back(u);
}
// Function to calculate height of
// each Node
void dfs1(int cur, int par)
{
// Iterate in the adjacency
// list of the current node
for (auto u : adj[cur]) {
if (u != par) {
// Dfs for child node
dfs1(u, cur);
// Calculate height of nodes
height[cur]
= max(height[cur], height[u]);
}
}
// Increase height
height[cur] += 1;
}
// Function to calculate the maximum
// distance of a node from its ancestor
void dfs2(int cur, int par)
{
int max1 = 0;
int max2 = 0;
// Iterate in the adjacency
// list of the current node
for (auto u : adj[cur]) {
if (u != par) {
// Find two children
// with maximum heights
if (height[u] >= max1) {
max2 = max1;
max1 = height[u];
}
else if (height[u] > max2) {
max2 = height[u];
}
}
}
int sum = 0;
for (auto u : adj[cur]) {
if (u != par) {
// Calculate the maximum distance
// with ancestor for every node
sum = ((max1 == height[u]) ? max2 : max1);
if (max1 == height[u])
dist[u]
= 1 + max(1 + max2, dist[cur]);
else
dist[u]
= 1 + max(1 + max1, dist[cur]);
// Calculating for children
dfs2(u, cur);
}
}
}
// Driver Code
int main()
{
int n = 6;
addEdge(1, 2);
addEdge(2, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(5, 6);
// Calculate height of
// nodes of the tree
dfs1(1, 0);
// Calculate the maximum
// distance with ancestors
dfs2(1, 0);
// Print the maximum of the two
// distances from each node
for (int i = 1; i <= n; i++)
cout << (max(dist[i], height[i]) - 1) << " ";
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
static final int maxN = 100001;
// Adjacency List to store the graph
@SuppressWarnings("unchecked")
static Vector<Integer> []adj = new Vector[maxN];
// Stores the height of each node
static int []height = new int[maxN];
// Stores the maximum distance of a
// node from its ancestors
static int []dist = new int[maxN];
// Function to add edge between
// two vertices
static void addEdge(int u, int v)
{
// Insert edge from u to v
adj[u].add(v);
// Insert edge from v to u
adj[v].add(u);
}
// Function to calculate height of
// each Node
static void dfs1(int cur, int par)
{
// Iterate in the adjacency
// list of the current node
for(int u : adj[cur])
{
if (u != par)
{
// Dfs for child node
dfs1(u, cur);
// Calculate height of nodes
height[cur] = Math.max(height[cur],
height[u]);
}
}
// Increase height
height[cur] += 1;
}
// Function to calculate the maximum
// distance of a node from its ancestor
static void dfs2(int cur, int par)
{
int max1 = 0;
int max2 = 0;
// Iterate in the adjacency
// list of the current node
for(int u : adj[cur])
{
if (u != par)
{
// Find two children
// with maximum heights
if (height[u] >= max1)
{
max2 = max1;
max1 = height[u];
}
else if (height[u] > max2)
{
max2 = height[u];
}
}
}
int sum = 0;
for(int u : adj[cur])
{
if (u != par)
{
// Calculate the maximum distance
// with ancestor for every node
sum = ((max1 == height[u]) ?
max2 : max1);
if (max1 == height[u])
dist[u] = 1 + Math.max(1 + max2,
dist[cur]);
else
dist[u] = 1 + Math.max(1 + max1,
dist[cur]);
// Calculating for children
dfs2(u, cur);
}
}
}
// Driver Code
public static void main(String[] args)
{
int n = 6;
for(int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
addEdge(1, 2);
addEdge(2, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(5, 6);
// Calculate height of
// nodes of the tree
dfs1(1, 0);
// Calculate the maximum
// distance with ancestors
dfs2(1, 0);
// Print the maximum of the two
// distances from each node
for(int i = 1; i <= n; i++)
System.out.print((Math.max(dist[i],
height[i]) - 1) + " ");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to implement # the above approach maxN = 100001 # Adjacency List to store the graph adj = [[] for i in range(maxN)] # Stores the height of each node height = [0 for i in range(maxN)] # Stores the maximum distance of a # node from its ancestors dist = [0 for i in range(maxN)] # Function to add edge between # two vertices def addEdge(u, v): # Insert edge from u to v adj[u].append(v) # Insert edge from v to u adj[v].append(u) # Function to calculate height of # each Node def dfs1(cur, par): # Iterate in the adjacency # list of the current node for u in adj[cur]: if (u != par): # Dfs for child node dfs1(u, cur) # Calculate height of nodes height[cur] = max(height[cur], height[u]) # Increase height height[cur] += 1 # Function to calculate the maximum # distance of a node from its ancestor def dfs2(cur, par): max1 = 0 max2 = 0 # Iterate in the adjacency # list of the current node for u in adj[cur]: if (u != par): # Find two children # with maximum heights if (height[u] >= max1): max2 = max1 max1 = height[u] elif (height[u] > max2): max2 = height[u] sum = 0 for u in adj[cur]: if (u != par): # Calculate the maximum distance # with ancestor for every node sum = (max2 if (max1 == height[u]) else max1) if (max1 == height[u]): dist[u] = 1 + max(1 + max2, dist[cur]) else: dist[u] = 1 + max(1 + max1, dist[cur]) # Calculating for children dfs2(u, cur) # Driver Code if __name__=="__main__": n = 6 addEdge(1, 2) addEdge(2, 3) addEdge(2, 4) addEdge(2, 5) addEdge(5, 6) # Calculate height of # nodes of the tree dfs1(1, 0) # Calculate the maximum # distance with ancestors dfs2(1, 0) # Print the maximum of the two # distances from each node for i in range(1, n + 1): print(max(dist[i], height[i]) - 1, end = ' ') # This code is contributed by rutvik_56
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG{
static readonly int maxN = 100001;
// Adjacency List to store the graph
static List<int> []adj = new List<int>[maxN];
// Stores the height of each node
static int []height = new int[maxN];
// Stores the maximum distance of a
// node from its ancestors
static int []dist = new int[maxN];
// Function to add edge between
// two vertices
static void addEdge(int u, int v)
{
// Insert edge from u to v
adj[u].Add(v);
// Insert edge from v to u
adj[v].Add(u);
}
// Function to calculate height of
// each Node
static void dfs1(int cur, int par)
{
// Iterate in the adjacency
// list of the current node
foreach(int u in adj[cur])
{
if (u != par)
{
// Dfs for child node
dfs1(u, cur);
// Calculate height of nodes
height[cur] = Math.Max(height[cur],
height[u]);
}
}
// Increase height
height[cur] += 1;
}
// Function to calculate the maximum
// distance of a node from its ancestor
static void dfs2(int cur, int par)
{
int max1 = 0;
int max2 = 0;
// Iterate in the adjacency
// list of the current node
foreach(int u in adj[cur])
{
if (u != par)
{
// Find two children
// with maximum heights
if (height[u] >= max1)
{
max2 = max1;
max1 = height[u];
}
else if (height[u] > max2)
{
max2 = height[u];
}
}
}
int sum = 0;
foreach(int u in adj[cur])
{
if (u != par)
{
// Calculate the maximum distance
// with ancestor for every node
sum = ((max1 == height[u]) ?
max2 : max1);
if (max1 == height[u])
dist[u] = 1 + Math.Max(1 + max2,
dist[cur]);
else
dist[u] = 1 + Math.Max(1 + max1,
dist[cur]);
// Calculating for children
dfs2(u, cur);
}
}
}
// Driver Code
public static void Main(String[] args)
{
int n = 6;
for(int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
addEdge(1, 2);
addEdge(2, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(5, 6);
// Calculate height of
// nodes of the tree
dfs1(1, 0);
// Calculate the maximum
// distance with ancestors
dfs2(1, 0);
// Print the maximum of the two
// distances from each node
for(int i = 1; i <= n; i++)
Console.Write((Math.Max(dist[i],
height[i]) - 1) + " ");
}
}
// This code is contributed by Rohit_ranjan
Javascript
<script>
// JavaScript program to implement the above approach
let maxN = 100001;
// Adjacency List to store the graph
let adj = new Array(maxN);
adj.fill(0);
// Stores the height of each node
let height = new Array(maxN);
height.fill(0);
// Stores the maximum distance of a
// node from its ancestors
let dist = new Array(maxN);
dist.fill(0);
// Function to add edge between
// two vertices
function addEdge(u, v)
{
// Insert edge from u to v
adj[u].push(v);
// Insert edge from v to u
adj[v].push(u);
}
// Function to calculate height of
// each Node
function dfs1(cur, par)
{
// Iterate in the adjacency
// list of the current node
for(let u = 0; u < adj[cur].length; u++)
{
if (adj[cur][u] != par)
{
// Dfs for child node
dfs1(adj[cur][u], cur);
// Calculate height of nodes
height[cur] = Math.max(height[cur],
height[adj[cur][u]]);
}
}
// Increase height
height[cur] += 1;
}
// Function to calculate the maximum
// distance of a node from its ancestor
function dfs2(cur, par)
{
let max1 = 0;
let max2 = 0;
// Iterate in the adjacency
// list of the current node
for(let u = 0; u < adj[cur].length; u++)
{
if (adj[cur][u] != par)
{
// Find two children
// with maximum heights
if (height[adj[cur][u]] >= max1)
{
max2 = max1;
max1 = height[adj[cur][u]];
}
else if (height[adj[cur][u]] > max2)
{
max2 = height[adj[cur][u]];
}
}
}
let sum = 0;
for(let u = 0; u < adj[cur].length; u++)
{
if (adj[cur][u] != par)
{
// Calculate the maximum distance
// with ancestor for every node
sum = ((max1 == height[adj[cur][u]]) ?
max2 : max1);
if (max1 == height[adj[cur][u]])
dist[adj[cur][u]] = 1 + Math.max(1 + max2,
dist[cur]);
else
dist[adj[cur][u]] = 1 + Math.max(1 + max1,
dist[cur]);
// Calculating for children
dfs2(adj[cur][u], cur);
}
}
}
let n = 6;
for(let i = 0; i < adj.length; i++)
adj[i] = [];
addEdge(1, 2);
addEdge(2, 3);
addEdge(2, 4);
addEdge(2, 5);
addEdge(5, 6);
// Calculate height of
// nodes of the tree
dfs1(1, 0);
// Calculate the maximum
// distance with ancestors
dfs2(1, 0);
// Print the maximum of the two
// distances from each node
for(let i = 1; i <= n; i++)
document.write((Math.max(dist[i],
height[i]) - 1) + " ");
</script>
Producción:
3 2 3 3 2 3
Complejidad temporal: O(V+E)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pwnkumar0786 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA