Consulta de relación ascendiente-descendiente en un árbol

Posted on by Rudeus Greyrat

Dado un árbol enraizado con N vértices y N-1 aristas. Nos darán muchos pares de vértices u y v, necesitamos saber si u es un antepasado de v o no. El árbol dado tendrá su raíz en el vértice con índice 0. 

Ejemplos:

treeForAncestor1

u = 1    v = 6
we can see from above tree that node 
1 is ancestor of node 6 so the answer 
will be yes.

u = 1    v = 7
we can see from above tree that node 1 
is not an ancestor of node 7 so the
answer will be no.

Podemos resolver este problema usando la primera búsqueda en profundidad del árbol. Mientras hacemos dfs podemos observar una relación entre el orden en que visitamos un Node y sus ancestros. Si asignamos tiempo de entrada y tiempo de salida a cada Node al entrar y salir de ese Node en dfs, entonces podemos ver que para cada par de ancestro-descendiente el tiempo de entrada del ancestro es menor que el del descendiente y el tiempo de salida de el antepasado es más que el descendiente, por lo que usando esta relación podemos encontrar el resultado para cada par de Nodes en el tiempo O(1). 

Entonces, la complejidad de tiempo para el preprocesamiento será O(N) y para la consulta será O(1). 

C++

// C++ program to query whether two node has
// ancestor-descendant relationship or not
#include <bits/stdc++.h>
using namespace std;
 
// Utility dfs method to assign in and out time
// to each node
void dfs(vector<int> g[], int u, int parent,
         int timeIn[], int timeOut[], int& cnt)
{
    // assign In-time to node u
    timeIn[u] = cnt++;
 
    // call dfs over all neighbors except parent
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v != parent)
            dfs(g, v, u, timeIn, timeOut, cnt);
    }
 
    // assign Out-time to node u
    timeOut[u] = cnt++;
}
 
// method to preprocess all nodes for assigning time
void preProcess(int edges[][2], int V, int timeIn[],
                int timeOut[])
{
    vector<int> g[V];
 
    // construct array of vector data structure
    // for tree
    for (int i = 0; i < V - 1; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
 
        g[u].push_back(v);
        g[v].push_back(u);
    }
 
    int cnt = 0;
 
    // call dfs method from root
    dfs(g, 0, -1, timeIn, timeOut, cnt);
}
 
// method returns "yes" if u is a ancestor
// node of v
string isAncestor(int u, int v, int timeIn[],
                  int timeOut[])
{
    bool b = (timeIn[u] <= timeIn[v] &&
             timeOut[v] <= timeOut[u]);
    return (b ? "yes" : "no");
}
 
// Driver code to test abovea methods
int main()
{
    int edges[][2] = {
        { 0, 1 },
        { 0, 2 },
        { 1, 3 },
        { 1, 4 },
        { 2, 5 },
        { 4, 6 },
        { 5, 7 }
    };
 
    int E = sizeof(edges) / sizeof(edges[0]);
    int V = E + 1;
 
    int timeIn[V], timeOut[V];
    preProcess(edges, V, timeIn, timeOut);
 
    int u = 1;
    int v = 6;
    cout << isAncestor(u, v, timeIn, timeOut) << endl;
 
    u = 1;
    v = 7;
    cout << isAncestor(u, v, timeIn, timeOut) << endl;
 
    return 0;
}

Java

// Java program to query whether two node has
// ancestor-descendant relationship or not
import java.util.Vector;
 
class GFG
{
  static int cnt;
 
  // Utility dfs method to assign in and out time
  // to each node
  static void dfs(Vector<Integer> []g, int u, int parent,
                  int []timeIn, int []timeOut)
  {
 
    // Assign In-time to node u
    timeIn[u] = cnt++;
 
    // Call dfs over all neighbors except parent
    for(int i = 0; i < g[u].size(); i++)
    {
      int v = g[u].get(i);       
      if (v != parent)
        dfs(g, v, u, timeIn, timeOut);
    }
 
    // Assign Out-time to node u
    timeOut[u] = cnt++;
  }
 
  // Method to preprocess all nodes for assigning time
  static void preProcess(int [][]edges, int V,
                         int []timeIn, int []timeOut)
  {
    @SuppressWarnings("unchecked")
    Vector<Integer> []g = new Vector[V];
    for (int i = 0; i < g.length; i++)
      g[i] = new Vector<Integer>();
 
    // Conarray of vector data structure
    // for tree
    for(int i = 0; i < V - 1; i++)
    {
      int u = edges[i][0];
      int v = edges[i][1];
      g[u].add(v);
      g[v].add(u);
    }
    cnt = 0;
 
    // Call dfs method from root
    dfs(g, 0, -1, timeIn, timeOut);
  }
 
  // Method returns "yes" if u is a ancestor
  // node of v
  static String isAncestor(int u, int v, int []timeIn,
                           int []timeOut)
  {
    boolean b = (timeIn[u] <= timeIn[v] &&
                 timeOut[v] <= timeOut[u]);
    return (b ? "yes" : "no");
  }
 
  // Driver code   
  public static void main(String[] args)
  {
    int edges[][] = { { 0, 1 },
                     { 0, 2 },
                     { 1, 3 },
                     { 1, 4 },
                     { 2, 5 },
                     { 4, 6 },
                     { 5, 7 } };   
    int E = edges.length;
    int V = E + 1;  
    int []timeIn = new int[V];
    int []timeOut = new int[V];  
    preProcess(edges, V, timeIn, timeOut);   
    int u = 1;
    int v = 6;
    System.out.println(isAncestor(u, v, timeIn,
                                  timeOut));   
    u = 1;
    v = 7;
    System.out.println(isAncestor(u, v, timeIn,
                                  timeOut));
  }
}
 
// This code is contributed by gauravrajput1

Python3

# Python program to query whether two node has
# ancestor-descendant relationship or not
 
cnt = 0
 
# Utility dfs method to assign in and out time
# to each node
def dfs(g: list, u: int, parent: int, timeIn: list, timeOut: list):
    global cnt
 
    # assign In-time to node u
    timeIn[u] = cnt
    cnt += 1
 
    # call dfs over all neighbors except parent
    for i in range(len(g[u])):
        v = g[u][i]
        if v != parent:
            dfs(g, v, u, timeIn, timeOut)
 
    # assign Out-time to node u
    timeOut[u] = cnt
    cnt += 1
 
# method to preprocess all nodes for assigning time
def preProcess(edges: list, V: int, timeIn: list, timeOut: list):
    global cnt
    g = [[] for i in range(V)]
 
    # construct array of vector data structure
    # for tree
    for i in range(V - 1):
        u = edges[i][0]
        v = edges[i][1]
 
        g[u].append(v)
        g[v].append(u)
 
    cnt = 0
 
    # call dfs method from root
    dfs(g, 0, -1, timeIn, timeOut)
 
# method returns "yes" if u is a ancestor
# node of v
def isAncestor(u: int, v: int, timeIn: list, timeOut: list) -> str:
    b = timeIn[u] <= timeIn[u] and timeOut[v] <= timeOut[u]
    return "yes" if b else "no"
 
# Driver Code
if __name__ == "__main__":
    edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (4, 6), (5, 7)]
    E = len(edges)
    V = E + 1
 
    timeIn = [0] * V
    timeOut = [0] * V
    preProcess(edges, V, timeIn, timeOut)
 
    u = 1
    v = 6
    print(isAncestor(u, v, timeIn, timeOut))
 
    u = 1
    v = 7
    print(isAncestor(u, v, timeIn, timeOut))
 
# This code is contributed by
# sanjeev2552

C#

// C# program to query whether two node has
// ancestor-descendant relationship or not
using System;
using System.Collections;
 
class GFG{
 
// Utility dfs method to assign in and out time
// to each node
static void dfs(ArrayList []g, int u, int parent,
                int []timeIn, int []timeOut,
                ref int cnt)
{
     
    // Assign In-time to node u
    timeIn[u] = cnt++;
  
    // Call dfs over all neighbors except parent
    for(int i = 0; i < g[u].Count; i++)
    {
        int v = (int)g[u][i];
         
        if (v != parent)
            dfs(g, v, u, timeIn, timeOut, ref cnt);
    }
  
    // Assign Out-time to node u
    timeOut[u] = cnt++;
}
  
// Method to preprocess all nodes for assigning time
static void preProcess(int [,]edges, int V,
                       int []timeIn, int []timeOut)
{
    ArrayList []g = new ArrayList[V];
     
    for(int i = 0; i < V; i++)
    {
        g[i] = new ArrayList();
    }
  
    // Construct array of vector data structure
    // for tree
    for(int i = 0; i < V - 1; i++)
    {
        int u = edges[i, 0];
        int v = edges[i, 1];
  
        g[u].Add(v);
        g[v].Add(u);
    }
  
    int cnt = 0;
  
    // Call dfs method from root
    dfs(g, 0, -1, timeIn, timeOut, ref cnt);
}
  
// Method returns "yes" if u is a ancestor
// node of v
static string isAncestor(int u, int v, int []timeIn,
                                       int []timeOut)
{
    bool b = (timeIn[u] <= timeIn[v] &&
             timeOut[v] <= timeOut[u]);
    return (b ? "yes" : "no");
}
     
// Driver code   
static void Main()
{
    int [,]edges = { { 0, 1 },
                     { 0, 2 },
                     { 1, 3 },
                     { 1, 4 },
                     { 2, 5 },
                     { 4, 6 },
                     { 5, 7 } };
     
    int E = edges.GetLength(0);
    int V = E + 1;
     
    int []timeIn = new int[V];
    int []timeOut = new int[V];
     
    preProcess(edges, V, timeIn, timeOut);
     
    int u = 1;
    int v = 6;
    Console.Write(isAncestor(u, v, timeIn,
                             timeOut) + "\n");
     
    u = 1;
    v = 7;
    Console.Write(isAncestor(u, v, timeIn,
                             timeOut) + "\n");
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
 
// Javascript program to query whether
// two node has ancestor-descendant
// relationship or not
let cnt;
 
// Utility dfs method to assign in and out time
// to each node
function dfs(g, u, parent, timeIn, timeOut)
{
     
    // Assign In-time to node u
    timeIn[u] = cnt++;
     
    // Call dfs over all neighbors except parent
    for(let i = 0; i < g[u].length; i++)
    {
        let v = g[u][i];      
        if (v != parent)
            dfs(g, v, u, timeIn, timeOut);
    }
     
    // Assign Out-time to node u
    timeOut[u] = cnt++;
}
 
// Method to preprocess all nodes for assigning time
function preProcess(edges, V, timeIn, timeOut)
{
    let g = new Array(V);
    for(let i = 0; i < g.length; i++)
        g[i] = [];
     
    // Conarray of vector data structure
    // for tree
    for(let i = 0; i < V - 1; i++)
    {
        let u = edges[i][0];
        let v = edges[i][1];
        g[u].push(v);
        g[v].push(u);
    }
    cnt = 0;
     
    // Call dfs method from root
    dfs(g, 0, -1, timeIn, timeOut);
}
 
// Method returns "yes" if u is a ancestor
// node of v
function isAncestor(u, v, timeIn, timeOut)
{
    let b = (timeIn[u] <= timeIn[v] &&
             timeOut[v] <= timeOut[u]);
    return (b ? "yes" : "no");
}
 
// Driver code
let edges = [ [ 0, 1 ], [ 0, 2 ],
              [ 1, 3 ], [ 1, 4 ],
              [ 2, 5 ], [ 4, 6 ],
              [ 5, 7 ] ];  
let E = edges.length;
let V = E + 1; 
let timeIn = new Array(V);
let timeOut = new Array(V); 
preProcess(edges, V, timeIn, timeOut);
 
let u = 1;
let v = 6;
document.write(isAncestor(u, v, timeIn,
                          timeOut) + "</br>");  
u = 1;
v = 7;
document.write(isAncestor(u, v, timeIn,
                          timeOut));
                           
// This code is contributed by divyeshrabadiya07
 
</script>

Producción: 

yes
no

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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

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

Deja una respuesta

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