Dado un árbol con N vértices numerados de 0 a N – 1 y Q consultas que contienen Nodes en el árbol, la tarea es encontrar la distancia del Node dado desde el Node raíz para múltiples consultas. Considere el Node 0 como el Node raíz y tome la distancia del Node raíz de sí mismo como 0.
Ejemplos:
Tree:
0
/ \
1 2
| / \
3 4 5
Input: 2
Output: 1
Explanation:
Distance of node 2 from root is 1
Input: 3
Output: 2
Explanation:
Distance of node 3 from root is 2
Enfoque:
Comience asignando la distancia del Node raíz como 0. Luego, atraviese el árbol usando Breadth First Traversal (BFS). Al marcar los hijos del Node N como visitados, asigne también la distancia de estos hijos como la distancia[N] + 1. Finalmente, para diferentes consultas, se imprime el valor de la array de distancia del Node.
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 representation
// of the tree
vector<int> tree[sz + 1];
// Boolean array to mark all the
// vertices which are visited
bool vis[sz + 1];
// Array of vector where ith index
// stores the path from the root
// node to the ith node
int dis[sz + 1];
// 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);
}
// Modified Breadth-First Function
void bfs(int node)
{
// Create a queue of {child, parent}
queue<pair<int, int> > qu;
// Push root node in the front of
qu.push({ node, 0 });
dis[0] = 0;
while (!qu.empty()) {
pair<int, int> p = qu.front();
// Dequeue a vertex from queue
qu.pop();
vis[p.first] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then enqueue it
for (int child : tree[p.first]) {
if (!vis[child]) {
dis[child] = dis[p.first] + 1;
qu.push({ child, p.first });
}
}
}
}
// Driver code
int main()
{
// Number of vertices
int n = 6;
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
// Calling modified bfs function
bfs(0);
int q[] = { 2, 4 };
for (int i = 0; i < 2; i++) {
cout << dis[q[i]] << '\n';
}
return 0;
}
Java
// Java implementation for
// the above approach
import java.util.*;
class GFG
{
static int sz = (int) 1e5;
// Adjacency list representation
// of the tree
static Vector<Integer> []tree = new Vector[sz + 1];
// Boolean array to mark all the
// vertices which are visited
static boolean []vis = new boolean[sz + 1];
// Array of vector where ith index
// stores the path from the root
// node to the ith node
static int []dis = new int[sz + 1];
static class pair
{
int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// 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);
}
// Modified Breadth-First Function
static void bfs(int node)
{
// Create a queue of {child, parent}
Queue<pair> qu = new LinkedList<>();
// Push root node in the front of
qu.add(new pair(node, 0 ));
dis[0] = 0;
while (!qu.isEmpty())
{
pair p = qu.peek();
// Dequeue a vertex from queue
qu.remove();
vis[p.first] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then enqueue it
for (int child : tree[p.first])
{
if (!vis[child])
{
dis[child] = dis[p.first] + 1;
qu.add(new pair(child, p.first));
}
}
}
}
// Driver code
public static void main(String[] args)
{
// Number of vertices
int n = 6;
for (int i = 0; i < sz + 1; i++)
tree[i] = new Vector<Integer>();
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
// Calling modified bfs function
bfs(0);
int q[] = { 2, 3 };
for (int i = 0; i < 2; i++)
{
System.out.println(dis[q[i]]);
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python implementation for
# the above approach
from collections import deque
sz = int(1e5)
# Adjacency list representation
# of the tree
tree = [0] * (sz + 1)
for i in range(sz + 1):
tree[i] = []
# Boolean array to mark all the
# vertices which are visited
vis = [False] * (sz + 1)
# Array of vector where ith index
# stores the path from the root
# node to the ith node
dis = [0] * sz
# Function to create an
# edge between two vertices
def addEdge(a: int, b: int):
global tree
# Add a to b's list
tree[a].append(b)
# Add b to a's list
tree[b].append(a)
# Modified Breadth-First Function
def bfs(node: int):
global dis, vis
# Create a queue of {child, parent}
qu = deque()
# Push root node in the front of
qu.append((node, 0))
dis[0] = 0
while qu:
p = qu[0]
# Dequeue a vertex from queue
qu.popleft()
vis[p[0]] = True
# Get all adjacent vertices of the dequeued
# vertex s. If any adjacent has not
# been visited then enqueue it
for child in tree[p[0]]:
if not vis[child]:
dis[child] = dis[p[0]] + 1
qu.append((child, p[0]))
# Driver Code
if __name__ == "__main__":
# Number of vertices
n = 6
addEdge(0, 1)
addEdge(0, 2)
addEdge(1, 3)
addEdge(2, 4)
addEdge(2, 5)
# Calling modified bfs function
bfs(0)
q = [2, 4]
for i in range(2):
print(dis[q[i]])
# This code is contributed by
# sanjeev2552
C#
// C# implementation for
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
static int sz = (int) 1e5;
// Adjacency list representation
// of the tree
static List<int> []tree = new List<int>[sz + 1];
// Boolean array to mark all the
// vertices which are visited
static Boolean []vis = new Boolean[sz + 1];
// Array of vector where ith index
// stores the path from the root
// node to the ith node
static int []dis = new int[sz + 1];
public class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// 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);
}
// Modified Breadth-First Function
static void bfs(int node)
{
// Create a queue of {child, parent}
Queue<pair> qu = new Queue<pair>();
// Push root node in the front of
qu.Enqueue(new pair(node, 0 ));
dis[0] = 0;
while (qu.Count != 0)
{
pair p = qu.Peek();
// Dequeue a vertex from queue
qu.Dequeue();
vis[p.first] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then enqueue it
foreach (int child in tree[p.first])
{
if (!vis[child])
{
dis[child] = dis[p.first] + 1;
qu.Enqueue(new pair(child, p.first));
}
}
}
}
// Driver code
public static void Main(String[] args)
{
// Number of vertices
for (int i = 0; i < sz + 1; i++)
tree[i] = new List<int>();
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
// Calling modified bfs function
bfs(0);
int []q = { 2, 3 };
for (int i = 0; i < 2; i++)
{
Console.WriteLine(dis[q[i]]);
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation for the above approach
let sz = 1e5;
// Adjacency list representation
// of the tree
let tree = new Array(sz + 1);
// Boolean array to mark all the
// vertices which are visited
let vis = new Array(sz + 1);
// Array of vector where ith index
// stores the path from the root
// node to the ith node
let dis = new Array(sz + 1);
// 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);
}
// Modified Breadth-First Function
function bfs(node)
{
// Create a queue of {child, parent}
let qu = [];
// Push root node in the front of
qu.push([node, 0]);
dis[0] = 0;
while (qu.length > 0)
{
let p = qu[0];
// Dequeue a vertex from queue
qu.shift();
vis[p[0]] = true;
// Get all adjacent vertices of the dequeued
// vertex s. If any adjacent has not
// been visited then enqueue it
for (let child = 0; child < tree[p[0]].length; child++)
{
if (!vis[tree[p[0]][child]])
{
dis[tree[p[0]][child]] = dis[p[0]] + 1;
qu.push([tree[p[0]][child], p[0]]);
}
}
}
}
// Number of vertices
let n = 6;
for (let i = 0; i < sz + 1; i++)
tree[i] = [];
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 3);
addEdge(2, 4);
addEdge(2, 5);
// Calling modified bfs function
bfs(0);
let q = [ 2, 3 ];
for (let i = 0; i < 2; i++)
{
document.write(dis[q[i]] + "</br>");
}
</script>
Producción:
1 2