Encuentre si la longitud de la ruta es par o impar entre los Nodes de árbol dados para consultas Q

Posted on by Rudeus Greyrat

Dado un árbol genérico que consta de N Nodes y (N – 1) aristas y una array de consultas consulta[] de tamaño Q que consta del tipo {A, B} , la tarea de cada consulta es verificar si la longitud de la ruta entre dos dados los Nodes A y B es par o impar.

Ejemplos:

Entrada: consulta[] = {{2, 4}, {4, 0}}

Salida: par
impar Explicación: para la primera consulta A = 2 y B = 4. La ruta de A a B es 2 -> 0 -> 1 -> 3 -> 4 con una longitud de 5, es decir, impar. Para la segunda consulta A = 4 y B = 0. La ruta de A a B es 4 -> 3 -> 1 -> 0 con una longitud de 4, es decir, Par.

Enfoque: el problema dado se puede resolver de manera eficiente al convertir el árbol en un gráfico bipartito . Se puede observar que si los Nodes A y B dados en una consulta están en el mismo lado en el gráfico bipartito construido, entonces la longitud del camino entre A y B debe ser impar y si A y B están en lados diferentes, entonces el camino la longitud debe ser impar. A continuación se detallan los pasos a seguir:

  • Recorre el árbol dado usando BFS Traversal .
  • Divida todos los Nodes en 2 conjuntos de modo que los dos Nodes adyacentes en el árbol estén en conjuntos diferentes (es decir, 0 o 1 ). Para hacerlo, asigne un número de conjunto alterno a cada nivel durante el recorrido BFS asignando el número de conjunto de Nodes actuales = 1 X O el número del padre del Node actual .
  • Después de completar los pasos anteriores, recorra la array dada de consultas query[] y si el número establecido de ambos Nodes es el mismo, la longitud de la ruta de A a B es impar . De lo contrario, es Even .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores the input tree
vector<vector<int> > adj(100000);
 
// Stores the set number of all nodes
vector<int> setNum(100000);
 
// Function to add an edge in the tree
void addEdge(int a1, int a2)
{
    adj[a1].push_back(a2);
    adj[a2].push_back(a1);
}
 
// Function to convert the given tree
// into a bipartite graph using BFS
void toBipartite(int N)
{
    // Set the set number to -1 for
    // all node of the given tree
    setNum.assign(N, -1);
 
    // Stores the current node during
    // the BFS traversal of the tree
    queue<int> q;
 
    // Initialize the set number of
    // 1st node and enqueue it
    q.push(0);
    setNum[0] = 0;
 
    // BFS traversal of the given tree
    while (!q.empty()) {
 
        // Current node
        int v = q.front();
        q.pop();
 
        // Traverse over all neighbours
        // of the current node
        for (int u : adj[v]) {
 
            // If the set is not assigned
            if (setNum[u] == -1) {
 
                // Assign set number to node u
                setNum[u] = setNum[v] ^ 1;
                q.push(u);
            }
        }
    }
}
 
// Function to find if the path length
// between node A and B is even or odd
void pathLengthQuery(int A, int B)
{
    // If the set number of both nodes is
    // same, path length is odd else even
    if (setNum[A] == setNum[B]) {
        cout << "Odd" << endl;
    }
    else {
        cout << "Even" << endl;
    }
}
 
// Driver Code
int main()
{
    int N = 7;
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(3, 4);
    addEdge(3, 5);
    addEdge(2, 6);
 
    // Function to convert tree into
    // bipartite
    toBipartite(N);
 
    pathLengthQuery(4, 2);
    pathLengthQuery(0, 4);
 
    return 0;
}

Java

// Java program for the above approach
 
import java.io.*;
import java.util.*;
 
class GFG {
   
// Stores the input tree
@SuppressWarnings("unchecked")
static Vector<Integer> []adj = new Vector[100000];
 
// Stores the set number of all nodes
static Vector<Integer> setNum = new Vector<Integer>(100000);
 
// Function to add an edge in the tree
static void addEdge(int a1, int a2)
{
    adj[a1].add(a2);
    adj[a2].add(a1);
}
 
// Function to convert the given tree
// into a bipartite graph using BFS
static void toBipartite(int N)
{
    // Set the set number to -1 for
    // all node of the given tree
    for (int i = 0; i < 100000; i++)
       setNum.add(-1);
 
    // Stores the current node during
    // the BFS traversal of the tree
    Queue<Integer> q
            = new LinkedList<>();
 
    // Initialize the set number of
    // 1st node and enqueue it
    q.add(0);
    setNum.set(0, 0);
 
    // BFS traversal of the given tree
    while (!q.isEmpty()) {
 
        // Current node
        int v = q.peek();
        q.remove();
 
        // Traverse over all neighbours
        // of the current node
        for (int u : adj[v]) {
 
            // If the set is not assigned
            if (setNum.get(u) == -1) {
 
                // Assign set number to node u
                  setNum.set(u, setNum.get(v) ^ 1);
                q.add(u);
            }
        }
    }
}
 
// Function to find if the path length
// between node A and B is even or odd
static void pathLengthQuery(int A, int B)
{
    // If the set number of both nodes is
    // same, path length is odd else even
    if (setNum.get(A) == setNum.get(B)) {
        System.out.println("Odd");
    }
    else {
        System.out.println("Even");
    }
}
 
// Driver Code
public static void main (String[] args) {
       
      for (int i = 0; i < 100000; i++)
       adj[i] = new Vector<Integer>();
   
    int N = 7;
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(3, 4);
    addEdge(3, 5);
    addEdge(2, 6);
 
    // Function to convert tree into
    // bipartite
    toBipartite(N);
 
    pathLengthQuery(4, 2);
    pathLengthQuery(0, 4);
}
}
 
// This code is contributed by Dharanendra L V.

Python3

# Python program for the above approach
from queue import Queue
 
# Stores the input tree
adj = [[0] * 100000] * 100000
 
# Stores the set number of all nodes
setNum = [0] * 100000
 
# Function to add an edge in the tree
def addEdge(a1, a2):
    adj[a1].append(a2);
    adj[a2].append(a1);
 
 
# Function to convert the given tree
# into a bipartite graph using BFS
def toBipartite(N):
   
    # Set the set number to -1 for
    # all node of the given tree
    for i in range(0, N):
        setNum[i] = -1
 
    # Stores the current node during
    # the BFS traversal of the tree
    q = Queue();
 
    # Initialize the set number of
    # 1st node and enqueue it
    q.put(0);
    setNum[0] = 0;
 
    # BFS traversal of the given tree
    while (not q.empty()):
 
        # Current node
        v = q.queue[0];
        q.get();
 
        # Traverse over all neighbours
        # of the current node
        for u in adj[v]:
 
            # If the set is not assigned
            if (setNum[u] == -1):
 
                # Assign set number to node u
                setNum[u] = setNum[v] ^ 1;
                q.put(u);
             
 
# Function to find if the path length
# between node A and B is even or odd
def pathLengthQuery(A, B):
    # If the set number of both nodes is
    # same, path length is odd else even
    if (setNum[A] == setNum[B]):
        print("Odd");
    else:
        print("Even");
 
# Driver Code
N = 7;
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(3, 4);
addEdge(3, 5);
addEdge(2, 6);
 
    # Function to convert tree into
    # bipartite
toBipartite(N);
 
pathLengthQuery(4, 2);
pathLengthQuery(0, 4);
 
# This code is contributed by _saurabh_jaiswal.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
   
// Stores the input tree
static List<int> []adj = new List<int>[100000];
 
// Stores the set number of all nodes
static List<int> setNum = new List<int>(100000);
 
// Function to add an edge in the tree
static void addEdge(int a1, int a2)
{
    adj[a1].Add(a2);
    adj[a2].Add(a1);
}
 
// Function to convert the given tree
// into a bipartite graph using BFS
static void toBipartite(int N)
{
   
    // Set the set number to -1 for
    // all node of the given tree
    for (int i = 0; i < 100000; i++)
       setNum.Add(-1);
 
    // Stores the current node during
    // the BFS traversal of the tree
    Queue<int> q
            = new Queue<int>();
 
    // Initialize the set number of
    // 1st node and enqueue it
    q.Enqueue(0);
    setNum[0] =  0;
 
    // BFS traversal of the given tree
    while (q.Count!=0) {
 
        // Current node
        int v = q.Peek();
        q.Dequeue();
 
        // Traverse over all neighbours
        // of the current node
        foreach (int u in adj[v]) {
 
            // If the set is not assigned
            if (setNum[u] == -1) {
 
                // Assign set number to node u
                  setNum[u] = ( setNum[v] ^ 1);
                q.Enqueue(u);
            }
        }
    }
}
 
// Function to find if the path length
// between node A and B is even or odd
static void pathLengthQuery(int A, int B)
{
   
    // If the set number of both nodes is
    // same, path length is odd else even
    if (setNum[A] == setNum[B])
    {
        Console.WriteLine("Odd");
    }
    else
    {
        Console.WriteLine("Even");
    }
}
 
// Driver Code
public static void Main(String[] args) {
       
      for (int i = 0; i < 100000; i++)
       adj[i] = new List<int>();
   
    int N = 7;
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(1, 3);
    addEdge(3, 4);
    addEdge(3, 5);
    addEdge(2, 6);
 
    // Function to convert tree into
    // bipartite
    toBipartite(N);
 
    pathLengthQuery(4, 2);
    pathLengthQuery(0, 4);
}
}
 
// This code is contributed by shikhasingrajput
Producción: 

Odd
Even

 

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

Publicación traducida automáticamente

Artículo escrito por bjsreddy742002 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 *