Dado un árbol conectado no dirigido con N Nodes (y N-1 aristas), necesitamos encontrar dos caminos en este árbol que no se intersequen y que el producto de su longitud sea máximo.
Ejemplos:
In first tree two paths which are non-intersecting and have highest product are, 1-2 and 3-4, so answer is 1*1 = 1 In second tree two paths which are non-intersecting and has highest product are, 1-3-5 and 7-8-6-2 (or 4-8-6-2), so answer is 3*2 = 6
Podemos resolver este problema mediante la primera búsqueda profunda del árbol procediendo de la siguiente manera, dado que el árbol está conectado y los caminos no se cruzan, si tomamos un par de tales caminos, debe haber un tercer camino, conectando estos dos y si eliminamos un borde de la tercera ruta, el árbol se dividirá en dos componentes: uno que contiene la primera ruta y el otro que contiene la segunda ruta. Esta observación nos sugiere el algoritmo: iterar sobre los bordes; para cada borde quítelo, encuentre la longitud del camino en ambos componentes conectados y multiplique las longitudes de estos caminos. La longitud de la ruta en un árbol se puede encontrar mediante la búsqueda primero en profundidad modificada, donde solicitaremos la ruta máxima en cada vecino y agregaremos dos longitudes máximas devueltas, que serán la longitud máxima de la ruta en el subárbol enraizado en el Node actual.
Detalles de implementacion:
La entrada es un árbol, pero no hay una raíz específica en él, ya que solo tenemos una colección de bordes. El árbol se representa como un gráfico no dirigido. Atravesamos la lista de adyacencia. Para cada borde, encontramos rutas de longitud máxima en ambos lados (después de eliminar el borde). Realizamos un seguimiento del producto máximo causado por la eliminación de un borde.
C++
// C++ program to find maximum product of two
// non-intersecting paths
#include <bits/stdc++.h>
using namespace std;
/* Returns maximum length path in subtree rooted
at u after removing edge connecting u and v */
int dfs(vector<int> g[], int& curMax, int u, int v)
{
// To find lengths of first and second maximum
// in subtrees. currMax is to store overall
// maximum.
int max1 = 0, max2 = 0, total = 0;
// loop through all neighbors of u
for (int i = 0; i < g[u].size(); i++)
{
// if neighbor is v, then skip it
if (g[u][i] == v)
continue;
// call recursively with current neighbor as root
total = max(total, dfs(g, curMax, g[u][i], u));
// get max from one side and update
if (curMax > max1)
{
max2 = max1;
max1 = curMax;
}
else
max2 = max(max2, curMax);
}
// store total length by adding max
// and second max
total = max(total, max1 + max2);
// update current max by adding 1, i.e.
// current node is included
curMax = max1 + 1;
return total;
}
// method returns maximum product of length of
// two non-intersecting paths
int maxProductOfTwoPaths(vector<int> g[], int N)
{
int res = INT_MIN;
int path1, path2;
// one by one removing all edges and calling
// dfs on both subtrees
for (int i = 1; i < N+2; i++)
{
for (int j = 0; j < g[i].size(); j++)
{
// calling dfs on subtree rooted at
// g[i][j], excluding edge from g[i][j]
// to i.
int curMax = 0;
path1 = dfs(g, curMax, g[i][j], i);
// calling dfs on subtree rooted at
// i, edge from i to g[i][j]
curMax = 0;
path2 = dfs(g, curMax, i, g[i][j]);
res = max(res, path1 * path2);
}
}
return res;
}
// Utility function to add an undirected edge (u,v)
void addEdge(vector<int> g[], int u, int v)
{
g[u].push_back(v);
g[v].push_back(u);
}
// Driver code to test above methods
int main()
{
int edges[][2] = {{1, 8}, {2, 6}, {3, 1},
{5, 3}, {7, 8}, {8, 4},
{8, 6} };
int N = sizeof(edges)/sizeof(edges[0]);
// there are N edges, so +1 for nodes and +1
// for 1-based indexing
vector<int> g[N + 2];
for (int i = 0; i < N; i++)
addEdge(g, edges[i][0], edges[i][1]);
cout << maxProductOfTwoPaths(g, N) << endl;
return 0;
}
Java
// Java program to find maximum product
// of two non-intersecting paths
import java.util.*;
class GFG{
static int curMax;
// Returns maximum length path in
// subtree rooted at u after
// removing edge connecting u and v
static int dfs(Vector<Integer> g[],
int u, int v)
{
// To find lengths of first and
// second maximum in subtrees.
// currMax is to store overall
// maximum.
int max1 = 0, max2 = 0, total = 0;
// Loop through all neighbors of u
for(int i = 0; i < g[u].size(); i++)
{
// If neighbor is v, then skip it
if (g[u].get(i) == v)
continue;
// Call recursively with current
// neighbor as root
total = Math.max(total, dfs(
g, g[u].get(i), u));
// Get max from one side and update
if (curMax > max1)
{
max2 = max1;
max1 = curMax;
}
else
max2 = Math.max(max2, curMax);
}
// Store total length by adding max
// and second max
total = Math.max(total, max1 + max2);
// Update current max by adding 1, i.e.
// current node is included
curMax = max1 + 1;
return total;
}
// Method returns maximum product of
// length of two non-intersecting paths
static int maxProductOfTwoPaths(Vector<Integer> g[],
int N)
{
int res = Integer.MIN_VALUE;
int path1, path2;
// One by one removing all edges and
// calling dfs on both subtrees
for(int i = 1; i < N + 2; i++)
{
for(int j = 0; j < g[i].size(); j++)
{
// Calling dfs on subtree rooted at
// g[i][j], excluding edge from g[i][j]
// to i.
curMax = 0;
path1 = dfs(g, g[i].get(j), i);
// Calling dfs on subtree rooted at
// i, edge from i to g[i][j]
curMax = 0;
path2 = dfs(g,i, g[i].get(j));
res = Math.max(res, path1 * path2);
}
}
return res;
}
// Utility function to add an
// undirected edge (u,v)
static void addEdge(Vector<Integer> g[],
int u, int v)
{
g[u].add(v);
g[v].add(u);
}
// Driver code
public static void main(String[] args)
{
int edges[][] = { { 1, 8 }, { 2, 6 },
{ 3, 1 }, { 5, 3 },
{ 7, 8 }, { 8, 4 },
{ 8, 6 } };
int N = edges.length;
// There are N edges, so +1 for nodes
// and +1 for 1-based indexing
@SuppressWarnings("unchecked")
Vector<Integer> []g = new Vector[N + 2];
for(int i = 0; i < g.length; i++)
g[i] = new Vector<Integer>();
for(int i = 0; i < N; i++)
addEdge(g, edges[i][0], edges[i][1]);
System.out.print(maxProductOfTwoPaths(g, N) + "\n");
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find maximum product of two # non-intersecting paths # Returns maximum length path in subtree rooted # at u after removing edge connecting u and v def dfs(g, curMax, u, v): # To find lengths of first and second maximum # in subtrees. currMax is to store overall # maximum. max1 = 0 max2 = 0 total = 0 # loop through all neighbors of u for i in range(len(g[u])): # if neighbor is v, then skip it if (g[u][i] == v): continue # call recursively with current neighbor as root total = max(total, dfs(g, curMax, g[u][i], u)) # get max from one side and update if (curMax[0] > max1): max2 = max1 max1 = curMax[0] else: max2 = max(max2, curMax[0]) # store total length by adding max # and second max total = max(total, max1 + max2) # update current max by adding 1, i.e. # current node is included curMax[0] = max1 + 1 return total # method returns maximum product of length of # two non-intersecting paths def maxProductOfTwoPaths(g, N): res = -999999999999 path1, path2 = None, None # one by one removing all edges and calling # dfs on both subtrees for i in range(N): for j in range(len(g[i])): # calling dfs on subtree rooted at # g[i][j], excluding edge from g[i][j] # to i. curMax = [0] path1 = dfs(g, curMax, g[i][j], i) # calling dfs on subtree rooted at # i, edge from i to g[i][j] curMax = [0] path2 = dfs(g, curMax, i, g[i][j]) res = max(res, path1 * path2) return res # Utility function to add an undirected edge (u,v) def addEdge(g, u, v): g[u].append(v) g[v].append(u) # Driver code if __name__ == '__main__': edges = [[1, 8], [2, 6], [3, 1], [5, 3], [7, 8], [8, 4], [8, 6]] N = len(edges) # there are N edges, so +1 for nodes and +1 # for 1-based indexing g = [[] for i in range(N + 2)] for i in range(N): addEdge(g, edges[i][0], edges[i][1]) print(maxProductOfTwoPaths(g, N)) # This code is contributed by PranchalK
C#
// C# program to find maximum product
// of two non-intersecting paths
using System;
using System.Collections.Generic;
public class GFG
{
static int curMax;
// Returns maximum length path in
// subtree rooted at u after
// removing edge connecting u and v
static int dfs(List<int> []g,
int u, int v)
{
// To find lengths of first and
// second maximum in subtrees.
// currMax is to store overall
// maximum.
int max1 = 0, max2 = 0, total = 0;
// Loop through all neighbors of u
for(int i = 0; i < g[u].Count; i++)
{
// If neighbor is v, then skip it
if (g[u][i] == v)
continue;
// Call recursively with current
// neighbor as root
total = Math.Max(total, dfs(
g, g[u][i], u));
// Get max from one side and update
if (curMax > max1)
{
max2 = max1;
max1 = curMax;
}
else
max2 = Math.Max(max2, curMax);
}
// Store total length by adding max
// and second max
total = Math.Max(total, max1 + max2);
// Update current max by adding 1, i.e.
// current node is included
curMax = max1 + 1;
return total;
}
// Method returns maximum product of
// length of two non-intersecting paths
static int maxProductOfTwoPaths(List<int> []g,
int N)
{
int res = int.MinValue;
int path1, path2;
// One by one removing all edges and
// calling dfs on both subtrees
for(int i = 1; i < N + 2; i++)
{
for(int j = 0; j < g[i].Count; j++)
{
// Calling dfs on subtree rooted at
// g[i,j], excluding edge from g[i,j]
// to i.
curMax = 0;
path1 = dfs(g, g[i][j], i);
// Calling dfs on subtree rooted at
// i, edge from i to g[i,j]
curMax = 0;
path2 = dfs(g,i, g[i][j]);
res = Math.Max(res, path1 * path2);
}
}
return res;
}
// Utility function to add an
// undirected edge (u,v)
static void addEdge(List<int> []g,
int u, int v)
{
g[u].Add(v);
g[v].Add(u);
}
// Driver code
public static void Main(String[] args)
{
int [,]edges = { { 1, 8 }, { 2, 6 },
{ 3, 1 }, { 5, 3 },
{ 7, 8 }, { 8, 4 },
{ 8, 6 } };
int N = edges.GetLength(0);
// There are N edges, so +1 for nodes
// and +1 for 1-based indexing
List<int> []g = new List<int>[N + 2];
for(int i = 0; i < g.Length; i++)
g[i] = new List<int>();
for(int i = 0; i < N; i++)
addEdge(g, edges[i,0], edges[i,1]);
Console.Write(maxProductOfTwoPaths(g, N) + "\n");
}
}
// This code is contributed by aashish1995
Javascript
<script>
// Javascript program to find maximum product of two
// non-intersecting paths
let curMax;
// Returns maximum length path in
// subtree rooted at u after
// removing edge connecting u and v
function dfs(g, u, v)
{
// To find lengths of first and
// second maximum in subtrees.
// currMax is to store overall
// maximum.
let max1 = 0, max2 = 0, total = 0;
// Loop through all neighbors of u
for(let i = 0; i < g[u].length; i++)
{
// If neighbor is v, then skip it
if (g[u][i] == v)
continue;
// Call recursively with current
// neighbor as root
total = Math.max(total, dfs(
g, g[u][i], u));
// Get max from one side and update
if (curMax > max1)
{
max2 = max1;
max1 = curMax;
}
else
max2 = Math.max(max2, curMax);
}
// Store total length by adding max
// and second max
total = Math.max(total, max1 + max2);
// Update current max by adding 1, i.e.
// current node is included
curMax = max1 + 1;
return total;
}
// Method returns maximum product of
// length of two non-intersecting paths
function maxProductOfTwoPaths(g, N)
{
let res = Number.MIN_VALUE;
let path1, path2;
// One by one removing all edges and
// calling dfs on both subtrees
for(let i = 1; i < N + 2; i++)
{
for(let j = 0; j < g[i].length; j++)
{
// Calling dfs on subtree rooted at
// g[i,j], excluding edge from g[i,j]
// to i.
curMax = 0;
path1 = dfs(g, g[i][j], i);
// Calling dfs on subtree rooted at
// i, edge from i to g[i,j]
curMax = 0;
path2 = dfs(g,i, g[i][j]);
res = Math.max(res, path1 * path2);
}
}
return res;
}
// Utility function to add an
// undirected edge (u,v)
function addEdge(g, u, v)
{
g[u].push(v);
g[v].push(u);
}
let edges = [ [ 1, 8 ], [ 2, 6 ],
[ 3, 1 ], [ 5, 3 ],
[ 7, 8 ], [ 8, 4 ],
[ 8, 6 ] ];
let N = edges.length;
// There are N edges, so +1 for nodes
// and +1 for 1-based indexing
let g = [];
for(let i = 0; i < N + 2; i++)
{
g.push([]);
}
for(let i = 0; i < g.length; i++)
g[i] = [];
for(let i = 0; i < N; i++)
addEdge(g, edges[i][0], edges[i][1]);
document.write(maxProductOfTwoPaths(g, N) + "</br>");
// This code is contributed by divyesh072019.
</script>
Producción
6
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA