Dado un árbol con N Nodes, la tarea es encontrar un triplete de Nodes (a, b, c) tal que el número de Nodes cubiertos en la ruta que conecta estos Nodes sea el máximo. (Cuenta un Node solo una vez).
Ejemplos:
Entrada: N = 4
Conjunto de aristas:
1 2
1 3
1 4
Salida: (2, 3, 4)
(2, 3, 4) como ruta entre (2, 3) cubre los Nodes 2, 1, 3 y la ruta entre (3 , 4) cubre los Nodes 3, 1, 4. Por lo tanto, todos los Nodes están cubiertos.
La ruta roja en el árbol indica la ruta entre 2 y 3 Nodes que cubre los Nodes 1, 2, 3. La ruta verde indica la ruta entre (3, 4) que cubre los Nodes 3, 1, 4. Entrada: N = 9 Conjunto
de bordes
:
1 2
2 3
3 4
4 5
5 6
2
7 7 8
4 9
Salida: (6, 8, 1)
Acercarse:
- Un punto importante a tener en cuenta es que dos de los puntos del triplete deben estar al final del diámetro del árbol para cubrir el máximo de los puntos.
- Necesitamos encontrar la rama de mayor longitud que se adhiera al diámetro.
- Ahora, para el tercer Node, aplique DFS junto con el mantenimiento de la profundidad de cada Node (DFS en todas las direcciones que no sean en la ruta de diámetro seleccionada) a todos los Nodes presentes en la ruta de diámetro, el Node que está a la distancia más lejana sería considerado como el 3er Node, ya que cubre el máximo Node distinto al ya cubierto por el Diámetro. Diámetro del árbol usando DFS
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
#define MAX 100005
using namespace std;
vector<int> adjacent[MAX];
bool visited[MAX];
// To store the required nodes
int startnode, endnode, thirdnode;
int maxi = -1, N;
// Parent array to retrace the nodes
int parent[MAX];
// Visited array to prevent DFS
// in direction on Diameter path
bool vis[MAX];
// DFS function to find the startnode
void dfs(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent[u].size(); i++) {
if (!visited[adjacent[u][i]]) {
temp++;
dfs(adjacent[u][i], count + 1);
}
}
if (temp == 0) {
if (maxi < count) {
maxi = count;
startnode = u;
}
}
}
// DFS function to find the endnode
// of diameter and maintain the parent array
void dfs1(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent[u].size(); i++) {
if (!visited[adjacent[u][i]]) {
temp++;
parent[adjacent[u][i]] = u;
dfs1(adjacent[u][i], count + 1);
}
}
if (temp == 0) {
if (maxi < count) {
maxi = count;
endnode = u;
}
}
}
// DFS function to find the end node
// of the Longest Branch to Diameter
void dfs2(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent[u].size(); i++) {
if (!visited[adjacent[u][i]]
&& !vis[adjacent[u][i]]) {
temp++;
dfs2(adjacent[u][i], count + 1);
}
}
if (temp == 0) {
if (maxi < count) {
maxi = count;
thirdnode = u;
}
}
}
// Function to find the required nodes
void findNodes()
{
// To find start node of diameter
dfs(1, 0);
for (int i = 0; i <= N; i++)
visited[i] = false;
maxi = -1;
// To find end node of diameter
dfs1(startnode, 0);
for (int i = 0; i <= N; i++)
visited[i] = false;
// x is the end node of diameter
int x = endnode;
vis[startnode] = true;
// Mark all the nodes on diameter
// using back tracking
while (x != startnode) {
vis[x] = true;
x = parent[x];
}
maxi = -1;
// Find the end node of longest
// branch to diameter
for (int i = 1; i <= N; i++) {
if (vis[i])
dfs2(i, 0);
}
}
// Driver code
int main()
{
N = 4;
adjacent[1].push_back(2);
adjacent[2].push_back(1);
adjacent[1].push_back(3);
adjacent[3].push_back(1);
adjacent[1].push_back(4);
adjacent[4].push_back(1);
findNodes();
cout << "(" << startnode << ", " << endnode
<< ", " << thirdnode << ")";
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 100005;
static Vector<Vector<Integer>> adjacent = new
Vector<Vector<Integer>> ();
static boolean visited[] = new boolean[MAX];
// To store the required nodes
static int startnode, endnode, thirdnode;
static int maxi = -1, N;
// Parent array to retrace the nodes
static int parent[] = new int[MAX];
// Visited array to prevent DFS
// in direction on Diameter path
static boolean vis[] = new boolean[MAX];
// DFS function to find the startnode
static void dfs(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent.get(u).size(); i++)
{
if (!visited[adjacent.get(u).get(i)])
{
temp++;
dfs(adjacent.get(u).get(i), count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
startnode = u;
}
}
}
// DFS function to find the endnode
// of diameter and maintain the parent array
static void dfs1(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent.get(u).size(); i++)
{
if (!visited[adjacent.get(u).get(i)])
{
temp++;
parent[adjacent.get(u).get(i)] = u;
dfs1(adjacent.get(u).get(i), count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
endnode = u;
}
}
}
// DFS function to find the end node
// of the Longest Branch to Diameter
static void dfs2(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent.get(u).size(); i++)
{
if (!visited[adjacent.get(u).get(i)] &&
!vis[adjacent.get(u).get(i)])
{
temp++;
dfs2(adjacent.get(u).get(i), count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
thirdnode = u;
}
}
}
// Function to find the required nodes
static void findNodes()
{
// To find start node of diameter
dfs(1, 0);
for (int i = 0; i <= N; i++)
visited[i] = false;
maxi = -1;
// To find end node of diameter
dfs1(startnode, 0);
for (int i = 0; i <= N; i++)
visited[i] = false;
// x is the end node of diameter
int x = endnode;
vis[startnode] = true;
// Mark all the nodes on diameter
// using back tracking
while (x != startnode)
{
vis[x] = true;
x = parent[x];
}
maxi = -1;
// Find the end node of longest
// branch to diameter
for (int i = 1; i <= N; i++)
{
if (vis[i])
dfs2(i, 0);
}
}
// Driver code
public static void main(String args[])
{
for(int i = 0; i < MAX; i++)
adjacent.add(new Vector<Integer>());
N = 4;
adjacent.get(1).add(2);
adjacent.get(2).add(1);
adjacent.get(1).add(3);
adjacent.get(3).add(1);
adjacent.get(1).add(4);
adjacent.get(4).add(1);
findNodes();
System.out.print( "(" + startnode + ", " +
endnode + ", " +
thirdnode + ")");
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
MAX = 100005
adjacent = [[] for i in range(MAX)]
visited = [False] * MAX
# To store the required nodes
startnode = endnode = thirdnode = None
maxi, N = -1, None
# Parent array to retrace the nodes
parent = [None] * MAX
# Visited array to prevent DFS
# in direction on Diameter path
vis = [False] * MAX
# DFS function to find the startnode
def dfs(u, count):
visited[u] = True
temp = 0
global startnode, maxi
for i in range(0, len(adjacent[u])):
if not visited[adjacent[u][i]]:
temp += 1
dfs(adjacent[u][i], count + 1)
if temp == 0:
if maxi < count:
maxi = count
startnode = u
# DFS function to find the endnode of
# diameter and maintain the parent array
def dfs1(u, count):
visited[u] = True
temp = 0
global endnode, maxi
for i in range(0, len(adjacent[u])):
if not visited[adjacent[u][i]]:
temp += 1
parent[adjacent[u][i]] = u
dfs1(adjacent[u][i], count + 1)
if temp == 0:
if maxi < count:
maxi = count
endnode = u
# DFS function to find the end node
# of the Longest Branch to Diameter
def dfs2(u, count):
visited[u] = True
temp = 0
global thirdnode, maxi
for i in range(0, len(adjacent[u])):
if (not visited[adjacent[u][i]] and
not vis[adjacent[u][i]]):
temp += 1
dfs2(adjacent[u][i], count + 1)
if temp == 0:
if maxi < count:
maxi = count
thirdnode = u
# Function to find the required nodes
def findNodes():
# To find start node of diameter
dfs(1, 0)
global maxi
for i in range(0, N+1):
visited[i] = False
maxi = -1
# To find end node of diameter
dfs1(startnode, 0)
for i in range(0, N+1):
visited[i] = False
# x is the end node of diameter
x = endnode
vis[startnode] = True
# Mark all the nodes on diameter
# using back tracking
while x != startnode:
vis[x] = True
x = parent[x]
maxi = -1
# Find the end node of longest
# branch to diameter
for i in range(1, N+1):
if vis[i]:
dfs2(i, 0)
# Driver code
if __name__ == "__main__":
N = 4
adjacent[1].append(2)
adjacent[2].append(1)
adjacent[1].append(3)
adjacent[3].append(1)
adjacent[1].append(4)
adjacent[4].append(1)
findNodes()
print("({}, {}, {})".format(startnode, endnode, thirdnode))
# This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG {
static int MAX = 100005;
static List<List<int>> adjacent = new List<List<int>>();
static bool[] visited = new bool[MAX];
// To store the required nodes
static int startnode, endnode, thirdnode;
static int maxi = -1, N;
// Parent array to retrace the nodes
static int[] parent = new int[MAX];
// Visited array to prevent DFS
// in direction on Diameter path
static bool[] vis = new bool[MAX];
// DFS function to find the startnode
static void dfs(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent[u].Count; i++)
{
if (!visited[adjacent[u][i]])
{
temp++;
dfs(adjacent[u][i], count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
startnode = u;
}
}
}
// DFS function to find the endnode
// of diameter and maintain the parent array
static void dfs1(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent[u].Count; i++)
{
if (!visited[adjacent[u][i]])
{
temp++;
parent[adjacent[u][i]] = u;
dfs1(adjacent[u][i], count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
endnode = u;
}
}
}
// DFS function to find the end node
// of the Longest Branch to Diameter
static void dfs2(int u, int count)
{
visited[u] = true;
int temp = 0;
for (int i = 0; i < adjacent[u].Count; i++)
{
if (!visited[adjacent[u][i]] &&
!vis[adjacent[u][i]])
{
temp++;
dfs2(adjacent[u][i], count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
thirdnode = u;
}
}
}
// Function to find the required nodes
static void findNodes()
{
// To find start node of diameter
dfs(1, 0);
for (int i = 0; i <= N; i++)
visited[i] = false;
maxi = -1;
// To find end node of diameter
dfs1(startnode, 0);
for (int i = 0; i <= N; i++)
visited[i] = false;
// x is the end node of diameter
int x = endnode;
vis[startnode] = true;
// Mark all the nodes on diameter
// using back tracking
while (x != startnode)
{
vis[x] = true;
x = parent[x];
}
maxi = -1;
// Find the end node of longest
// branch to diameter
for (int i = 1; i <= N; i++)
{
if (vis[i])
dfs2(i, 0);
}
}
static void Main() {
for(int i = 0; i < MAX; i++)
adjacent.Add(new List<int>());
N = 4;
adjacent[1].Add(2);
adjacent[2].Add(1);
adjacent[1].Add(3);
adjacent[3].Add(1);
adjacent[1].Add(4);
adjacent[4].Add(1);
findNodes();
Console.WriteLine( "(" + startnode + ", " +
endnode + ", " +
thirdnode + ")");
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// JavaScript implementation of the approach
let MAX = 100005;
let adjacent = [];
let visited = new Array(MAX);
// To store the required nodes
let startnode, endnode, thirdnode;
let maxi = -1, N;
// Parent array to retrace the nodes
let parent = new Array(MAX);
// Visited array to prevent DFS
// in direction on Diameter path
let vis = new Array(MAX);
// DFS function to find the startnode
function dfs(u, count)
{
visited[u] = true;
let temp = 0;
for (let i = 0; i < adjacent[u].length; i++)
{
if (!visited[adjacent[u][i]])
{
temp++;
dfs(adjacent[u][i], count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
startnode = u;
}
}
}
// DFS function to find the endnode
// of diameter and maintain the parent array
function dfs1(u, count)
{
visited[u] = true;
let temp = 0;
for (let i = 0; i < adjacent[u].length; i++)
{
if (!visited[adjacent[u][i]])
{
temp++;
parent[adjacent[u][i]] = u;
dfs1(adjacent[u][i], count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
endnode = u;
}
}
}
// DFS function to find the end node
// of the Longest Branch to Diameter
function dfs2(u, count)
{
visited[u] = true;
let temp = 0;
for (let i = 0; i < adjacent[u].length; i++)
{
if (!visited[adjacent[u][i]] &&
!vis[adjacent[u][i]])
{
temp++;
dfs2(adjacent[u][i], count + 1);
}
}
if (temp == 0)
{
if (maxi < count)
{
maxi = count;
thirdnode = u;
}
}
}
// Function to find the required nodes
function findNodes()
{
// To find start node of diameter
dfs(1, 0);
for (let i = 0; i <= N; i++)
visited[i] = false;
maxi = -1;
// To find end node of diameter
dfs1(startnode, 0);
for (let i = 0; i <= N; i++)
visited[i] = false;
// x is the end node of diameter
let x = endnode;
vis[startnode] = true;
// Mark all the nodes on diameter
// using back tracking
while (x != startnode)
{
vis[x] = true;
x = parent[x];
}
maxi = -1;
// Find the end node of longest
// branch to diameter
for (let i = 1; i <= N; i++)
{
if (vis[i])
dfs2(i, 0);
}
}
for(let i = 0; i < MAX; i++)
adjacent.push([]);
N = 4;
adjacent[1].push(2);
adjacent[2].push(1);
adjacent[1].push(3);
adjacent[3].push(1);
adjacent[1].push(4);
adjacent[4].push(1);
findNodes();
document.write( "(" + startnode + ", " +
endnode + ", " +
thirdnode + ")");
</script>
Producción:
(2, 3, 4)