Dado un árbol con N Nodes y (N-1) aristas y el Node de origen está en la primera posición . Hay consultas Q , cada una del tipo {pos, X, Y} . Realice la siguiente operación según el tipo de consulta:
- Si pos = 0 , encuentre si Y está presente en el subárbol de X.
- Si pos = 1 , encuentre si X está presente en el subárbol de Y.
Ejemplos:
Entrada: N: = 9, aristas = {{1, 2}, {1, 3}, {2, 6}, {2, 7}, {6, 9}, {7, 8}, {3, 4 }, {3, 5}}
Q = 5, consulta = {{0, 2, 8}, {1, 2, 8}, {1, 6, 5}, {0, 6, 5}, {1, 9, 1}}
Salida: {Sí, No, No, No, Sí}
Explicación: Vea la imagen a continuación.
8 está presente en el subárbol de 2 y 9 también está presente en el subárbol de 9.
Para las demás consultas no cumple la condición.
Entrada: N = 2, bordes = {{1, 2}}
Q = 1, consulta = {0, 2, 1}
Salida: {No}
Explicación: 1 no está presente en el subárbol de 2.
Planteamiento: La solución del problema se basa en el DFS . Tome el tiempo de entrada y salida para cada Node. Al usar esto, se puede verificar fácilmente si algún Node está presente en el subárbol de otro Node o no. Siga los pasos que se mencionan a continuación:
- En primer lugar, busque el tiempo de entrada (tiempo en el que estamos entrando en ese Node) y el tiempo de salida (tiempo en el que estamos saliendo de ese Node) para cada uno de los Nodes (inicialmente nuestro temporizador es 1) usando el recorrido DFS del árbol.
- Luego, para cada una de las consultas, según su tipo, encuentre si Y está presente en el subárbol de X o viceversa.
- Para verificar si Y está presente en el subárbol de X , verifique si el tiempo de entrada de Y es mayor que X y el tiempo de salida de Y es menor que X y todo lo contrario para verificar si X está presente en el subárbol de Y.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Initial timer=1
int timer = 1;
// Simple DFS Function
void dfs(vector<int> adj[], int itime[],
int otime[], int src, int par)
{
// While visiting a node
// mark its timer in time and
// increase timer for next nodes
itime[src] = timer++;
for (auto it : adj[src]) {
if (it != par) {
dfs(adj, itime, otime, it, src);
}
}
// While leaving a node
// mark its timer in out time
// and increase timer for next nodes
otime[src] = timer++;
}
// Check for subtree
bool check(int itime[], int otime[],
int x, int y)
{
// Intime of y should be more
// and outime should be less than x
if (itime[x] < itime[y]
&& otime[x] > otime[y])
return true;
return false;
}
// Function to solve the queries
void solve(int N, vector<vector<int> >& edges,
int Q, vector<vector<int> >& query)
{
vector<int> adj[N + 1];
// N-1 edges given
for (int i = 0; i < N - 1; i++) {
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
// Array for intime
int intime[N + 1];
// Array for outime
int outtime[N + 1];
// Using DFS function
// to find intime and outtime
dfs(adj, intime, outtime, 1, -1);
for (int i = 0; i < Q; i++) {
int type = query[i][0],
X = query[i][1],
Y = query[i][2];
if (type == 0) {
if (check(intime, outtime, X, Y)) {
// To check if Y is present
// in subtree of X
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
else {
if (check(intime, outtime, Y, X)) {
// To check if X is present
// in subtree of Y
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
}
}
// Driver code
int main()
{
int N = 9;
// N is the number of nodes
vector<vector<int> > edges
= { { 1, 2 }, { 1, 3 }, { 2, 6 },
{ 2, 7 }, { 6, 9 }, { 7, 8 },
{ 3, 4 }, { 3, 5 } };
int Q = 5;
vector<vector<int> > query = { { 0, 2, 8 },
{ 1, 2, 8 },
{ 1, 6, 5 },
{ 0, 6, 5 },
{ 1, 9, 1 } };
solve(N, edges, Q, query);
return 0;
}
Java
// Java program to implement the approach
import java.util.*;
class GFG{
// Initial timer=1
static int timer = 1;
// Simple DFS Function
static void dfs(Vector<Integer> adj[], int itime[],
int otime[], int src, int par)
{
// While visiting a node
// mark its timer in time and
// increase timer for next nodes
itime[src] = timer++;
for (int it : adj[src]) {
if (it != par) {
dfs(adj, itime, otime, it, src);
}
}
// While leaving a node
// mark its timer in out time
// and increase timer for next nodes
otime[src] = timer++;
}
// Check for subtree
static boolean check(int itime[], int otime[],
int x, int y)
{
// Intime of y should be more
// and outime should be less than x
if (itime[x] < itime[y]
&& otime[x] > otime[y])
return true;
return false;
}
// Function to solve the queries
static void solve(int N, int[][] edges,
int Q, int[][] query)
{
Vector<Integer> []adj = new Vector[N + 1];
for (int i = 0; i < adj.length; i++)
adj[i] = new Vector<Integer>();
// N-1 edges given
for (int i = 0; i < N - 1; i++) {
adj[edges[i][0]].add(edges[i][1]);
adj[edges[i][1]].add(edges[i][0]);
}
// Array for intime
int []intime = new int[N + 1];
// Array for outime
int []outtime = new int[N + 1];
// Using DFS function
// to find intime and outtime
dfs(adj, intime, outtime, 1, -1);
for (int i = 0; i < Q; i++) {
int type = query[i][0],
X = query[i][1],
Y = query[i][2];
if (type == 0) {
if (check(intime, outtime, X, Y)) {
// To check if Y is present
// in subtree of X
System.out.print("Yes" +"\n");
}
else {
System.out.print("No" +"\n");
}
}
else {
if (check(intime, outtime, Y, X)) {
// To check if X is present
// in subtree of Y
System.out.print("Yes" +"\n");
}
else {
System.out.print("No" +"\n");
}
}
}
}
// Driver code
public static void main(String[] args)
{
int N = 9;
// N is the number of nodes
int[][] edges
= { { 1, 2 }, { 1, 3 }, { 2, 6 },
{ 2, 7 }, { 6, 9 }, { 7, 8 },
{ 3, 4 }, { 3, 5 } };
int Q = 5;
int[][] query = { { 0, 2, 8 },
{ 1, 2, 8 },
{ 1, 6, 5 },
{ 0, 6, 5 },
{ 1, 9, 1 } };
solve(N, edges, Q, query);
}
}
// This code is contributed by 29AjayKumar
C#
// C# program to implement the approach
using System;
using System.Collections.Generic;
public class GFG{
// Initial timer=1
static int timer = 1;
// Simple DFS Function
static void dfs(List<int> []adj, int []itime,
int []otime, int src, int par)
{
// While visiting a node
// mark its timer in time and
// increase timer for next nodes
itime[src] = timer++;
foreach (int it in adj[src]) {
if (it != par) {
dfs(adj, itime, otime, it, src);
}
}
// While leaving a node
// mark its timer in out time
// and increase timer for next nodes
otime[src] = timer++;
}
// Check for subtree
static bool check(int []itime, int []otime,
int x, int y)
{
// Intime of y should be more
// and outime should be less than x
if (itime[x] < itime[y]
&& otime[x] > otime[y])
return true;
return false;
}
// Function to solve the queries
static void solve(int N, int[,] edges,
int Q, int[,] query)
{
List<int> []adj = new List<int>[N + 1];
for (int i = 0; i < adj.Length; i++)
adj[i] = new List<int>();
// N-1 edges given
for (int i = 0; i < N - 1; i++) {
adj[edges[i,0]].Add(edges[i,1]);
adj[edges[i,1]].Add(edges[i,0]);
}
// Array for intime
int []intime = new int[N + 1];
// Array for outime
int []outtime = new int[N + 1];
// Using DFS function
// to find intime and outtime
dfs(adj, intime, outtime, 1, -1);
for (int i = 0; i < Q; i++) {
int type = query[i,0],
X = query[i,1],
Y = query[i,2];
if (type == 0) {
if (check(intime, outtime, X, Y)) {
// To check if Y is present
// in subtree of X
Console.Write("Yes" +"\n");
}
else {
Console.Write("No" +"\n");
}
}
else {
if (check(intime, outtime, Y, X)) {
// To check if X is present
// in subtree of Y
Console.Write("Yes" +"\n");
}
else {
Console.Write("No" +"\n");
}
}
}
}
// Driver code
public static void Main(String[] args)
{
int N = 9;
// N is the number of nodes
int[,] edges
= { { 1, 2 }, { 1, 3 }, { 2, 6 },
{ 2, 7 }, { 6, 9 }, { 7, 8 },
{ 3, 4 }, { 3, 5 } };
int Q = 5;
int[,] query = { { 0, 2, 8 },
{ 1, 2, 8 },
{ 1, 6, 5 },
{ 0, 6, 5 },
{ 1, 9, 1 } };
solve(N, edges, Q, query);
}
}
// This code is contributed by Rajput-Ji
Producción
Yes No No No Yes
Complejidad temporal: O(max (N, Q))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por bansalashish2101 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA