Encuentre el Node U que contiene todos los Nodes de un conjunto V a una distancia máxima de 1 desde la ruta desde la raíz hasta U

Dado un árbol N-ario con N vértices enraizados en 1 y un conjunto de vértices como V[] , la tarea es imprimir cualquier vértice U tal que el camino desde la raíz hasta U consista en todos los vértices desde V[] como máximo distancia 1 . Si no se obtiene ningún vértice, imprima “No” . De lo contrario, imprima el valor de U .

Ejemplos:

Entrada: N = 10, Bordes[][] = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, { 7, 8}, {7, 9}, {9, 10}}, V[] = {4, 3, 8, 9, 10}

Salida: 10
Explicación: La ruta desde la raíz hasta el Node 10 contiene {1, 3, 7, 9, 10} y 8 está a la distancia 1 de esta ruta. 

Entrada: N = 10, Bordes[][] = {{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {3, 7}, { 7, 8}, {7, 9}, {9, 10}}, V[] = {3, 4, 2, 8}

Salida: 8
Explicación: La ruta desde la raíz hasta el Node 8 contiene {1, 3, 7, 8}. Ahora, 4 y 2 están a una distancia de 1 de este camino.

Enfoque ingenuo: la idea ingenua es encontrar todos los caminos posibles desde la raíz 1 a cada Node y elegir el que contiene todos los vértices requeridos del conjunto dado V[] en el camino desde la raíz hasta ese vértice elegido o tiene una distancia 1 de ese camino. 
Complejidad de Tiempo: O(N!) 
Espacio Auxiliar: O(N ² )

Enfoque eficiente: el enfoque anterior se puede optimizar calculando previamente las distancias de cada vértice desde la raíz . Este cálculo previo ayuda a encontrar si algún vértice P es padre de algún otro vértice C en el árbol dado o no. A continuación se muestran los pasos:

1. Realice DFS Traversal desde el Node raíz 1 y almacene el tiempo antes y después de la visita de cada Node en el árbol dado.
2. Ahora, el vértice V es el padre del vértice U si y solo si el tiempo previo de V es menor o igual que el tiempo previo de U y el tiempo posterior de U es mayor o igual que el tiempo posterior de V.
3. Se puede notar que el camino del vértice más profundo en el conjunto dado V[] desde el vértice raíz es el resultado requerido.
4. Ahora, el problema se reduce a verificar si el padre de cada vértice en el conjunto dado V[] es el antepasado del vértice más profundo en el conjunto V[] .
5. Por lo tanto, reemplace cada vértice con su padre (excepto la raíz ) y verifique que cada padre sea el antepasado del vértice más profundo según la propiedad mencionada anteriormente.
6. Si la condición se cumple, imprima el vértice más profundo; de lo contrario, imprima «No» .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// To store the time
int timeT = 0;
 
// Function to perform DFS
// to store times, distance
// and parent of each node
void dfs(int u, int p, int dis,
         vector<int>& vis,
         vector<int>& distance,
         vector<int>& parent,
         vector<int>& preTime,
         vector<int>& postTime,
         vector<int> Adj[])
{
    // Update the distance of node u
    distance[u] = dis;
 
    // Update parent of node u
    parent[u] = p;
    vis[u] = 1;
 
    // Increment time timeT
    timeT++;
 
    // Discovery time of node u
    preTime[u] = timeT;
 
    // Traverse the adjacency list
    // of current node and recursively
    // call DFS for each vertex
    for (int i = 0; i < Adj[u].size(); i++) {
 
        // If current node Adj[u][i]
        // is unvisited
        if (vis[Adj[u][i]] == 0) {
 
            dfs(Adj[u][i], u, dis + 1,
                vis, distance, parent,
                preTime, postTime, Adj);
        }
    }
 
    timeT++;
 
    // Update the finishing time
    postTime[u] = timeT;
}
 
// Function to add edges between
// nodes u and v
void addEdge(vector<int> Adj[],
             int u, int v)
{
    Adj[u].push_back(v);
    Adj[v].push_back(u);
}
 
// Function to find the node U
// such that path from root to U
// contains nodes in V[]
void findNodeU(int N, int V,
               int Vertices[],
               int Edges[][2])
{
 
    // Initialise vis, dis, parent,
    // preTime, and postTime
    vector<int> vis(N + 1, 0);
    vector<int> distance(N + 1, 0);
    vector<int> parent(N + 1, 0);
    vector<int> preTime(N + 1, 0);
    vector<int> postTime(N + 1, 0);
 
    // Store Adjacency List
    vector<int> Adj[N + 1];
 
    int u, v;
 
    // Create adjacency List
    for (int i = 0; i < N - 1; i++) {
        addEdge(Adj, Edges[i][0],
                Edges[i][1]);
    }
 
    // Perform DFS Traversal
    dfs(1, 0, 0, vis, distance, parent,
        preTime, postTime, Adj);
 
    int maximumDistance = 0;
 
    // Stores the distance
    // of deepest vertex 'u'
    maximumDistance = 0;
 
    // Update the deepest node by
    // traversing the qu[]
    for (int k = 0; k < V; k++) {
 
        // Find deepest vertex
        if (maximumDistance
            < distance[Vertices[k]]) {
 
            maximumDistance
                = distance[Vertices[k]];
            u = Vertices[k];
        }
 
        // Replace each vertex with it's
        // corresponding parent except
        // the root vertex
        if (parent[Vertices[k]] != 0) {
            Vertices[k]
                = parent[Vertices[k]];
        }
    }
 
    bool ans = true;
 
    bool flag;
 
    for (int k = 0; k < V; k++) {
 
        // Checks if the ancestor
        // with respect to deepest
        // vertex u
        if (preTime[Vertices[k]]
                <= preTime[u]
            && postTime[Vertices[k]]
                   >= postTime[u])
            flag = true;
        else
            flag = false;
 
        // Update ans
        ans = ans & flag;
    }
 
    // Print the result
    if (ans)
        cout << u;
    else
        cout << "NO";
}
 
// Driver Code
int main()
{
    // Total vertices
    int N = 10;
 
    int V = 5;
 
    // Given set of vertices
    int Vertices[] = { 4, 3, 8, 9, 10 };
 
    // Given edges
    int Edges[][2] = { { 1, 2 }, { 1, 3 },
                       { 1, 4 }, { 2, 5 },
                       { 2, 6 }, { 3, 7 },
                       { 7, 8 }, { 7, 9 }, 
                       { 9, 10 } };
 
    // Function Call
    findNodeU(N, V, Vertices, Edges);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// To store the time
static int timeT = 0;
 
// Function to perform DFS
// to store times, distance
// and parent of each node
static void dfs(int u, int p, int dis, int vis[],
                int distance[], int parent[],
                int preTime[], int postTime[],
                ArrayList<ArrayList<Integer>> Adj)
{
     
    // Update the distance of node u
    distance[u] = dis;
 
    // Update parent of node u
    parent[u] = p;
    vis[u] = 1;
 
    // Increment time timeT
    timeT++;
 
    // Discovery time of node u
    preTime[u] = timeT;
 
    // Traverse the adjacency list
    // of current node and recursively
    // call DFS for each vertex
    for(int i = 0; i < Adj.get(u).size(); i++)
    {
 
        // If current node Adj[u][i]
        // is unvisited
        if (vis[Adj.get(u).get(i)] == 0)
        {
            dfs(Adj.get(u).get(i), u, dis + 1,
                vis, distance, parent, preTime,
                postTime, Adj);
        }
    }
 
    timeT++;
 
    // Update the finishing time
    postTime[u] = timeT;
}
 
// Function to add edges between
// nodes u and v
static void addEdge(ArrayList<ArrayList<Integer>> Adj,
                    int u, int v)
{
    Adj.get(u).add(v);
    Adj.get(v).add(u);
}
 
// Function to find the node U
// such that path from root to U
// contains nodes in V[]
static void findNodeU(int N, int V,
                      int Vertices[],
                      int Edges[][])
{
 
    // Initialise vis, dis, parent,
    // preTime, and postTime
    int vis[] = new int[N + 1];
    int distance[] = new int[N + 1];
    int parent[] = new int[N + 1];
    int preTime[] = new int[N + 1];
    int postTime[] = new int[N + 1];
 
    // Store Adjacency List
    ArrayList<
    ArrayList<Integer>> Adj = new ArrayList<>();
    for(int i = 0; i < N + 1; i++)
        Adj.add(new ArrayList<Integer>());
         
    int u = 0, v;
 
    // Create adjacency List
    for(int i = 0; i < N - 1; i++)
    {
        addEdge(Adj, Edges[i][0], Edges[i][1]);
    }
 
    // Perform DFS Traversal
    dfs(1, 0, 0, vis, distance,
        parent, preTime, postTime, Adj);
 
    int maximumDistance = 0;
 
    // Stores the distance
    // of deepest vertex 'u'
    maximumDistance = 0;
 
    // Update the deepest node by
    // traversing the qu[]
    for(int k = 0; k < V; k++)
    {
 
        // Find deepest vertex
        if (maximumDistance <
            distance[Vertices[k]])
        {
            maximumDistance =
            distance[Vertices[k]];
            u = Vertices[k];
        }
 
        // Replace each vertex with it's
        // corresponding parent except
        // the root vertex
        if (parent[Vertices[k]] != 0)
        {
            Vertices[k] = parent[Vertices[k]];
        }
    }
 
    boolean ans = true;
    boolean flag;
 
    for(int k = 0; k < V; k++)
    {
 
        // Checks if the ancestor
        // with respect to deepest
        // vertex u
        if (preTime[Vertices[k]] <= preTime[u] &&
           postTime[Vertices[k]] >= postTime[u])
            flag = true;
        else
            flag = false;
 
        // Update ans
        ans = ans & flag;
    }
 
    // Print the result
    if (ans)
        System.out.println(u);
    else
        System.out.println("NO");
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Total vertices
    int N = 10;
 
    int V = 5;
 
    // Given set of vertices
    int Vertices[] = { 4, 3, 8, 9, 10 };
 
    // Given edges
    int Edges[][] = { { 1, 2 }, { 1, 3 },
                      { 1, 4 }, { 2, 5 },
                      { 2, 6 }, { 3, 7 },
                      { 7, 8 }, { 7, 9 },
                      { 9, 10 } };
 
    // Function call
    findNodeU(N, V, Vertices, Edges);
}
}
 
// This code is contributed by jrishabh99

# Python3 program for the above approach
  
# To store the time
timeT = 0;
  
# Function to perform DFS
# to store times, distance
# and parent of each node
def dfs(u, p, dis,
          vis,
          distance,
          parent,
          preTime,
          postTime,
          Adj):
     
    global timeT
     
    # Update the distance of node u
    distance[u] = dis;
  
    # Update parent of node u
    parent[u] = p;
    vis[u] = 1;
  
    # Increment time timeT
    timeT += 1
  
    # Discovery time of node u
    preTime[u] = timeT;
  
    # Traverse the adjacency list
    # of current node and recursively
    # call DFS for each vertex
    for i in range(len(Adj[u])):
  
        # If current node Adj[u][i]
        # is unvisited
        if (vis[Adj[u][i]] == 0):
  
            dfs(Adj[u][i], u, dis + 1,
                vis, distance, parent,
                preTime, postTime, Adj);
         
    timeT += 1
  
    # Update the finishing time
    postTime[u] = timeT;
 
# Function to add edges between
# nodes u and v
def addEdge(Adj,u, v):
 
    Adj[u].append(v);
    Adj[v].append(u);
  
# Function to find the node U
# such that path from root to U
# contains nodes in V[]
def findNodeU(N, V, Vertices, Edges):
  
    # Initialise vis, dis, parent,
    # preTime, and postTime
    vis = [0 for i in range(N + 1)]
    distance = [0 for i in range(N + 1)]
    parent = [0 for i in range(N + 1)]
    preTime = [0 for i in range(N + 1)]
    postTime = [0 for i in range(N + 1)]
  
    # Store Adjacency List
    Adj = [[] for i in range(N + 1)]
  
    u = 0
    v = 0
  
    # Create adjacency List
    for i in range(N - 1):
     
        addEdge(Adj, Edges[i][0],
                Edges[i][1]);
  
    # Perform DFS Traversal
    dfs(1, 0, 0, vis, distance, parent,
        preTime, postTime, Adj);
  
    maximumDistance = 0;
  
    # Stores the distance
    # of deepest vertex 'u'
    maximumDistance = 0;
  
    # Update the deepest node by
    # traversing the qu[]
    for k in range(V):
  
        # Find deepest vertex
        if (maximumDistance < distance[Vertices[k]]):
  
            maximumDistance= distance[Vertices[k]];
            u = Vertices[k];
  
        # Replace each vertex with it's
        # corresponding parent except
        # the root vertex
        if (parent[Vertices[k]] != 0):
            Vertices[k]= parent[Vertices[k]];
          
    ans = True;
  
    flag = False
     
    for k in range(V):
  
        # Checks if the ancestor
        # with respect to deepest
        # vertex u
        if (preTime[Vertices[k]] <= preTime[u]
                and postTime[Vertices[k]]
                   >= postTime[u]):
            flag = True;
        else:
            flag = False;
  
        # Update ans
        ans = ans & flag;
      
    # Print the result
    if (ans):
        print(u)
    else:
        print('No')
  
# Driver Code
if __name__=='__main__':
     
    # Total vertices
    N = 10;
  
    V = 5;
  
    # Given set of vertices
    Vertices = [ 4, 3, 8, 9, 10 ];
  
    # Given edges
    Edges = [ [ 1, 2 ], [ 1, 3 ],
                       [ 1, 4 ], [ 2, 5 ],
                       [ 2, 6 ], [ 3, 7 ],
                       [ 7, 8 ], [ 7, 9 ], 
                       [ 9, 10 ] ];
  
    # Function Call
    findNodeU(N, V, Vertices, Edges);
    
  # This code is contributed by rutvik_56

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
     
// To store the time
static int timeT = 0;
 
// Function to perform DFS
// to store times, distance
// and parent of each node
static void dfs(int u, int p, int dis, int []vis,
                int []distance, int []parent,
                int []preTime, int []postTime,
                List<List<int>> Adj)
{
  // Update the distance of node u
  distance[u] = dis;
 
  // Update parent of node u
  parent[u] = p;
  vis[u] = 1;
 
  // Increment time timeT
  timeT++;
 
  // Discovery time of node u
  preTime[u] = timeT;
 
  // Traverse the adjacency list
  // of current node and recursively
  // call DFS for each vertex
  for(int i = 0; i < Adj[u].Count; i++)
  {
    // If current node Adj[u,i]
    // is unvisited
    if (vis[Adj[u][i]] == 0)
    {
      dfs(Adj[u][i], u, dis + 1,
          vis, distance, parent, preTime,
          postTime, Adj);
    }
  }
 
  timeT++;
 
  // Update the finishing time
  postTime[u] = timeT;
}
 
// Function to add edges between
// nodes u and v
static void addEdge(List<List<int>> Adj,
                    int u, int v)
{
  Adj[u].Add(v);
  Adj[v].Add(u);
}
 
// Function to find the node U
// such that path from root to U
// contains nodes in V[]
static void findNodeU(int N, int V,
                      int []Vertices,
                      int [,]Edges)
{
  // Initialise vis, dis, parent,
  // preTime, and postTime
  int []vis = new int[N + 1];
  int []distance = new int[N + 1];
  int []parent = new int[N + 1];
  int []preTime = new int[N + 1];
  int []postTime = new int[N + 1];
 
  // Store Adjacency List
  List<List<int>> Adj = new List<List<int>>();
  for(int i = 0; i < N + 1; i++)
    Adj.Add(new List<int>());
 
  int u = 0, v;
 
  // Create adjacency List
  for(int i = 0; i < N - 1; i++)
  {
    addEdge(Adj, Edges[i, 0], Edges[i, 1]);
  }
 
  // Perform DFS Traversal
  dfs(1, 0, 0, vis, distance,
      parent, preTime, postTime, Adj);
 
  int maximumDistance = 0;
 
  // Stores the distance
  // of deepest vertex 'u'
  maximumDistance = 0;
 
  // Update the deepest node by
  // traversing the qu[]
  for(int k = 0; k < V; k++)
  {
    // Find deepest vertex
    if (maximumDistance <
        distance[Vertices[k]])
    {
      maximumDistance = distance[Vertices[k]];
      u = Vertices[k];
    }
 
    // Replace each vertex with it's
    // corresponding parent except
    // the root vertex
    if (parent[Vertices[k]] != 0)
    {
      Vertices[k] = parent[Vertices[k]];
    }
  }
 
  bool ans = true;
  bool flag;
 
  for(int k = 0; k < V; k++)
  {
    // Checks if the ancestor
    // with respect to deepest
    // vertex u
    if (preTime[Vertices[k]] <= preTime[u] &&
        postTime[Vertices[k]] >= postTime[u])
      flag = true;
    else
      flag = false;
 
    // Update ans
    ans = ans & flag;
  }
 
  // Print the result
  if (ans)
    Console.WriteLine(u);
  else
    Console.WriteLine("NO");
}
 
// Driver Code
public static void Main(String[] args)
{    
  // Total vertices
  int N = 10;
 
  int V = 5;
 
  // Given set of vertices
  int []Vertices = {4, 3, 8, 9, 10};
 
  // Given edges
  int [,]Edges = {{1, 2}, {1, 3},
                  {1, 4}, {2, 5},
                  {2, 6}, {3, 7},
                  {7, 8}, {7, 9},
                  {9, 10}};
 
  // Function call
  findNodeU(N, V, Vertices, Edges);
}
}
 
// This code is contributed by gauravrajput1

<script>
 
    // JavaScript implementation of the above approach
     
    // To store the time
    let timeT = 0;
 
    // Function to perform DFS
    // to store times, distance
    // and parent of each node
    function dfs(u, p, dis, vis, distance, parent,
    preTime, postTime, Adj)
    {
      // Update the distance of node u
      distance[u] = dis;
 
      // Update parent of node u
      parent[u] = p;
      vis[u] = 1;
 
      // Increment time timeT
      timeT++;
 
      // Discovery time of node u
      preTime[u] = timeT;
 
      // Traverse the adjacency list
      // of current node and recursively
      // call DFS for each vertex
      for(let i = 0; i < Adj[u].length; i++)
      {
        // If current node Adj[u,i]
        // is unvisited
        if (vis[Adj[u][i]] == 0)
        {
          dfs(Adj[u][i], u, dis + 1,
              vis, distance, parent, preTime,
              postTime, Adj);
        }
      }
 
      timeT++;
 
      // Update the finishing time
      postTime[u] = timeT;
    }
 
    // Function to add edges between
    // nodes u and v
    function addEdge(Adj, u, v)
    {
      Adj[u].push(v);
      Adj[v].push(u);
    }
 
    // Function to find the node U
    // such that path from root to U
    // contains nodes in V[]
    function findNodeU(N, V, Vertices, Edges)
    {
      // Initialise vis, dis, parent,
      // preTime, and postTime
      let vis = new Array(N + 1);
      vis.fill(0);
      let distance = new Array(N + 1);
      distance.fill(0);
      let parent = new Array(N + 1);
      parent.fill(0);
      let preTime = new Array(N + 1);
      preTime.fill(0);
      let postTime = new Array(N + 1);
      postTime.fill(0);
 
      // Store Adjacency List
      let Adj = [];
      for(let i = 0; i < N + 1; i++)
        Adj.push([]);
 
      let u = 0, v;
 
      // Create adjacency List
      for(let i = 0; i < N - 1; i++)
      {
        addEdge(Adj, Edges[i][0], Edges[i][1]);
      }
 
      // Perform DFS Traversal
      dfs(1, 0, 0, vis, distance,
          parent, preTime, postTime, Adj);
 
      let maximumDistance = 0;
 
      // Stores the distance
      // of deepest vertex 'u'
      maximumDistance = 0;
 
      // Update the deepest node by
      // traversing the qu[]
      for(let k = 0; k < V; k++)
      {
        // Find deepest vertex
        if (maximumDistance < distance[Vertices[k]])
        {
          maximumDistance = distance[Vertices[k]];
          u = Vertices[k];
        }
 
        // Replace each vertex with it's
        // corresponding parent except
        // the root vertex
        if (parent[Vertices[k]] != 0)
        {
          Vertices[k] = parent[Vertices[k]];
        }
      }
 
      let ans = true;
      let flag;
 
      for(let k = 0; k < V; k++)
      {
        // Checks if the ancestor
        // with respect to deepest
        // vertex u
        if (preTime[Vertices[k]] <= preTime[u] &&
            postTime[Vertices[k]] >= postTime[u])
          flag = true;
        else
          flag = false;
 
        // Update ans
        ans = ans & flag;
      }
 
      // Print the result
      if (ans)
        document.write(u);
      else
        document.write("NO");
    }
     
    // Total vertices
    let N = 10;
 
    let V = 5;
 
    // Given set of vertices
    let Vertices = [4, 3, 8, 9, 10];
 
    // Given edges
    let Edges = [[1, 2], [1, 3],
      [1, 4], [2, 5],
      [2, 6], [3, 7],
      [7, 8], [7, 9],
      [9, 10]];
 
    // Function call
    findNodeU(N, V, Vertices, Edges);
     
</script>

10

Complejidad temporal: O(N + V), donde N es el total de vértices y V es el tamaño del conjunto dado.
Espacio auxiliar: O(5*N)