Consultas para encontrar el recuento de rutas más cortas en un árbol que contiene un borde dado

Posted on by Rudeus Greyrat

Dado un árbol con N vértices numerados de 0 a N – 1, M aristas y Q consultas de la forma {U, V}, tal que haya una arista directa entre U y V en el árbol. La tarea de cada consulta es encontrar todos los caminos más cortos posibles entre cualquier posible par de vértices desordenados del árbol dado que contiene el borde entre el par de Nodes dado.

Ejemplos:

Entrada: N = 6, M[] ={{0, 1}, {0, 2}, {1, 3}, {3, 4}, {3, 5}}, consultas[] = {{1, 3}, {0, 2}}
                  0
                / \
             1 2
           /
         3
       / \
    4 5
Salida:
9
5
Explicación:
Consulta 1: El borde (1, 3) se encuentra en las rutas {1, 3), (1, 3 , 4), (1, 3, 5), (0, 3), (0, 4), (0, 5), (2, 3), (2, 4) y (2, 5).
Consulta 2: El borde (0, 2) se encuentra en las rutas (2, 0), (2, 1), (2, 3), (2, 4) y (2, 5).

Entrada: N = 6, M[] ={{0, 1}, {0, 2}, {2, 3}, {1, 4}, {1, 5}}, consultas[] = {{1, 5}, {0, 2}}
                  0
                / \
             1 2
           / \ /
        4 5 3
Salida:
5
8

Enfoque: el problema se puede resolver con base en la observación de que para cualquier consulta {U, V}, el camino más corto entre cualquier par de Nodes en el árbol contendrá el borde dado (U, V) si uno de los Nodes se encuentra en el subárbol de U y el otro Node se encuentra en el árbol restante. Por lo tanto, el número requerido de pares será:

Recuento de las rutas más cortas que contienen (U, V) como borde = subtreeSize(U) * (N – subtreeSize(V)). 

Por lo tanto, siga los pasos a continuación para resolver el problema:

  • Realice el recorrido de primera búsqueda en profundidad en el árbol a partir del Node raíz.
  • Para cada Node, almacene el recuento de Nodes en su subárbol (incluye el Node).
  • Iterar sobre cada consulta (U, V) y calcular:

min( tamaño del subárbol(U), tamaño del subárbol(V)) * ( N – min( tamaño del subárbol(U), tamaño del subárbol(V)) )

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int sz = 1e5;
 
// Adjacency list to
// represent the tree
vector<int> tree[sz];
 
// Number of vertices
int n;
 
// Mark visited/ unvisited
// vertices
bool vis[sz];
 
// Stores the subtree size
// of the corresponding nodes
int subtreeSize[sz];
 
// Function to create an
// edge between two vertices
void addEdge(int a, int b)
{
    // Add a to b's list
    tree[a].push_back(b);
 
    // Add b to a's list
    tree[b].push_back(a);
}
 
// Function to perform DFS
void dfs(int x)
{
    // Mark the vertex
    // visited
    vis[x] = true;
 
    // Include the node in
    // the subtree
    subtreeSize[x] = 1;
 
    // Traverse all its children
    for (auto i : tree[x]) {
        if (!vis[i]) {
            dfs(i);
            subtreeSize[x]
                += subtreeSize[i];
        }
    }
}
 
// Function to print the
// required number of paths
void countPairs(int a, int b)
{
    int sub = min(subtreeSize[a],
                  subtreeSize[b]);
 
    cout << sub * (n - sub)
         << endl;
}
 
// Driver Code
int main()
{
    // Number of vertices
    n = 6;
 
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(3, 4);
    addEdge(3, 5);
 
    // Calling modified dfs function
    dfs(0);
 
    // Count pairs of vertices in the tree
    countPairs(1, 3);
    countPairs(0, 2);
    return 0;
}

Java

// Java implementation for
// the above approach
import java.util.*;
class GFG{
 
static int sz = (int) 1e5;
 
// Adjacency list to
// represent the tree
static Vector<Integer> []tree = new Vector[sz];
 
// Number of vertices
static int n;
 
// Mark visited/ unvisited
// vertices
static boolean []vis = new boolean[sz];
 
// Stores the subtree size
// of the corresponding nodes
static int []subtreeSize = new int[sz];
 
// Function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
  // Add a to b's list
  tree[a].add(b);
 
  // Add b to a's list
  tree[b].add(a);
}
 
// Function to perform DFS
static void dfs(int x)
{
  // Mark the vertex
  // visited
  vis[x] = true;
 
  // Include the node in
  // the subtree
  subtreeSize[x] = 1;
 
  // Traverse all its children
  for (int i : tree[x])
  {
    if (!vis[i])
    {
      dfs(i);
      subtreeSize[x] += subtreeSize[i];
    }
  }
}
 
// Function to print the
// required number of paths
static void countPairs(int a, int b)
{
  int sub = Math.min(subtreeSize[a],
                     subtreeSize[b]);
 
  System.out.print(sub * (n - sub) + "\n");
}
 
// Driver Code
public static void main(String[] args)
{
  // Number of vertices
  n = 6;
  for (int i = 0; i < tree.length; i++)
    tree[i] = new Vector<Integer>();
  addEdge(0, 1);
  addEdge(0, 2);
  addEdge(1, 3);
  addEdge(3, 4);
  addEdge(3, 5);
 
  // Calling modified dfs function
  dfs(0);
 
  // Count pairs of vertices in the tree
  countPairs(1, 3);
  countPairs(0, 2);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation for
# the above approach
sz = 100000
 
# Adjacency list to
# represent the tree
tree = [[] for i in range(sz)]
 
# Number of vertices
n = 0
 
# Mark visited/ unvisited
# vertices
vis = [False] * sz
 
# Stores the subtree size
# of the corresponding nodes
subtreeSize = [0 for i in range(sz)]
 
# Function to create an
# edge between two vertices
def addEdge(a, b):
     
    global tree
     
    # Add a to b's list
    tree[a].append(b)
 
    # Add b to a's list
    tree[b].append(a)
 
# Function to perform DFS
def dfs(x):
     
    # Mark the vertex
    # visited
    global vis
    global subtreeSize
    global tree
    vis[x] = True
 
    # Include the node in
    # the subtree
    subtreeSize[x] = 1
 
    # Traverse all its children
    for i in tree[x]:
        if (vis[i] == False):
            dfs(i)
            subtreeSize[x] += subtreeSize[i]
 
# Function to print the
# required number of paths
def countPairs(a, b):
     
    global subtreeSize
    sub = min(subtreeSize[a],
              subtreeSize[b])
 
    print(sub * (n - sub))
 
# Driver Code
if __name__ == '__main__':
     
    # Number of vertices
    n = 6
     
    addEdge(0, 1)
    addEdge(0, 2)
    addEdge(1, 3)
    addEdge(3, 4)
    addEdge(3, 5)
 
    # Calling modified dfs function
    dfs(0)
 
    # Count pairs of vertices in the tree
    countPairs(1, 3)
    countPairs(0, 2)
 
# This code is contributed by SURENDRA_GANGWAR

C#

// C# implementation for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
   
static int sz = (int) 1e5;
 
// Adjacency list to
// represent the tree
static List<int> []tree =
            new List<int>[sz];
 
// Number of vertices
static int n;
 
// Mark visited/ unvisited
// vertices
static bool []vis = new bool[sz];
 
// Stores the subtree size
// of the corresponding nodes
static int []subtreeSize = new int[sz];
 
// Function to create an
// edge between two vertices
static void addEdge(int a, int b)
{
  // Add a to b's list
  tree[a].Add(b);
 
  // Add b to a's list
  tree[b].Add(a);
}
 
// Function to perform DFS
static void dfs(int x)
{
  // Mark the vertex
  // visited
  vis[x] = true;
 
  // Include the node in
  // the subtree
  subtreeSize[x] = 1;
 
  // Traverse all its children
  foreach (int i in tree[x])
  {
    if (!vis[i])
    {
      dfs(i);
      subtreeSize[x] += subtreeSize[i];
    }
  }
}
 
// Function to print the
// required number of paths
static void countPairs(int a, int b)
{
  int sub = Math.Min(subtreeSize[a],
                     subtreeSize[b]);
 
  Console.Write(sub * (n - sub) + "\n");
}
 
// Driver Code
public static void Main(String[] args)
{
  // Number of vertices
  n = 6;
  for (int i = 0; i < tree.Length; i++)
    tree[i] = new List<int>();
  addEdge(0, 1);
  addEdge(0, 2);
  addEdge(1, 3);
  addEdge(3, 4);
  addEdge(3, 5);
 
  // Calling modified dfs function
  dfs(0);
 
  // Count pairs of vertices in the tree
  countPairs(1, 3);
  countPairs(0, 2);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript implementation for the above approach
 
var sz = 100005;
 
// Adjacency list to
// represent the tree
var tree = Array.from(Array(sz), ()=> Array())
 
// Number of vertices
var n;
 
// Mark visited/ unvisited
// vertices
var vis = Array(sz);
 
// Stores the subtree size
// of the corresponding nodes
var subtreeSize = Array(sz);
 
// Function to create an
// edge between two vertices
function addEdge(a, b)
{
    // Add a to b's list
    tree[a].push(b);
 
    // Add b to a's list
    tree[b].push(a);
}
 
// Function to perform DFS
function dfs(x)
{
    // Mark the vertex
    // visited
    vis[x] = true;
 
    // Include the node in
    // the subtree
    subtreeSize[x] = 1;
 
    // Traverse all its children
    tree[x].forEach(i => {
         
        if (!vis[i]) {
            dfs(i);
            subtreeSize[x]
                += subtreeSize[i];
        }
    });
}
 
// Function to print the
// required number of paths
function countPairs(a, b)
{
    var sub = Math.min(subtreeSize[a],
                  subtreeSize[b]);
 
    document.write( sub * (n - sub) + "<br>");
}
 
// Driver Code
// Number of vertices
n = 6;
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(3, 4);
addEdge(3, 5);
// Calling modified dfs function
dfs(0);
// Count pairs of vertices in the tree
countPairs(1, 3);
countPairs(0, 2);
 
</script>
Producción: 

9
5

 

Complejidad temporal: O(N + M + Q)
Espacio auxiliar: O(N) 

Publicación traducida automáticamente

Artículo escrito por Pratims10 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *