Dado un entero k y un árbol con n Nodes. La tarea es contar el número de pares distintos de vértices que tienen una distancia de exactamente k .
Ejemplos:
Entrada: k = 2
Salida: 4
Entrada: k = 3
Salida: 2
Enfoque: Este problema se puede resolver mediante programación dinámica. Para cada vértice v del árbol, calculamos valores d[v][lev] (0 <= lev <= k). Este valor indica el número de vértices que tienen la distancia lev de v. Tenga en cuenta que d[v][0] = 1.
Luego calculamos la respuesta. Para cualquier vértice v, el número de pares será un producto del número de vértices en el nivel j – 1 y el nivel k – j.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 5005
// To store vertices and value of k
int n, k;
vector<int> gr[N];
// To store number vertices at a level i
int d[N][505];
// To store the final answer
int ans = 0;
// Function to add an edge between two nodes
void Add_edge(int x, int y)
{
gr[x].push_back(y);
gr[y].push_back(x);
}
// Function to find the number of distinct
// pairs of the vertices which have a distance
// of exactly k in a tree
void dfs(int v, int par)
{
// At level zero vertex itself is counted
d[v][0] = 1;
for (auto i : gr[v]) {
if (i != par) {
dfs(i, v);
// Count the pair of vertices at
// distance k
for (int j = 1; j <= k; j++)
ans += d[i][j - 1] * d[v][k - j];
// For all levels count vertices
for (int j = 1; j <= k; j++)
d[v][j] += d[i][j - 1];
}
}
}
// Driver code
int main()
{
n = 5, k = 2;
// Add edges
Add_edge(1, 2);
Add_edge(2, 3);
Add_edge(3, 4);
Add_edge(2, 5);
// Function call
dfs(1, 0);
// Required answer
cout << ans;
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static final int N = 5005;
// To store vertices and value of k
static int n, k;
static Vector<Integer>[] gr = new Vector[N];
// To store number vertices at a level i
static int[][] d = new int[N][505];
// To store the final answer
static int ans = 0;
// Function to add an edge between two nodes
static void Add_edge(int x, int y)
{
gr[x].add(y);
gr[y].add(x);
}
// Function to find the number of distinct
// pairs of the vertices which have a distance
// of exactly k in a tree
static void dfs(int v, int par)
{
// At level zero vertex itself is counted
d[v][0] = 1;
for (Integer i : gr[v])
{
if (i != par)
{
dfs(i, v);
// Count the pair of vertices at
// distance k
for (int j = 1; j <= k; j++)
ans += d[i][j - 1] * d[v][k - j];
// For all levels count vertices
for (int j = 1; j <= k; j++)
d[v][j] += d[i][j - 1];
}
}
}
// Driver code
public static void main(String[] args)
{
n = 5;
k = 2;
for (int i = 0; i < N; i++)
gr[i] = new Vector<Integer>();
// Add edges
Add_edge(1, 2);
Add_edge(2, 3);
Add_edge(3, 4);
Add_edge(2, 5);
// Function call
dfs(1, 0);
// Required answer
System.out.print(ans);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Python3 implementation of the approach N = 5005 # To store vertices and value of k n, k = 0, 0 gr = [[] for i in range(N)] # To store number vertices at a level i d = [[0 for i in range(505)] for i in range(N)] # To store the final answer ans = 0 # Function to add an edge between two nodes def Add_edge(x, y): gr[x].append(y) gr[y].append(x) # Function to find the number of distinct # pairs of the vertices which have a distance # of exactly k in a tree def dfs(v, par): global ans # At level zero vertex itself is counted d[v][0] = 1 for i in gr[v]: if (i != par): dfs(i, v) # Count the pair of vertices at # distance k for j in range(1, k + 1): ans += d[i][j - 1] * d[v][k - j] # For all levels count vertices for j in range(1, k + 1): d[v][j] += d[i][j - 1] # Driver code n = 5 k = 2 # Add edges Add_edge(1, 2) Add_edge(2, 3) Add_edge(3, 4) Add_edge(2, 5) # Function call dfs(1, 0) # Required answer print(ans) # This code is contributed by Mohit Kumar
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static readonly int N = 5005;
// To store vertices and value of k
static int n, k;
static List<int>[] gr = new List<int>[N];
// To store number vertices at a level i
static int[,] d = new int[N, 505];
// To store the readonly answer
static int ans = 0;
// Function to add an edge between two nodes
static void Add_edge(int x, int y)
{
gr[x].Add(y);
gr[y].Add(x);
}
// Function to find the number of distinct
// pairs of the vertices which have a distance
// of exactly k in a tree
static void dfs(int v, int par)
{
// At level zero vertex itself is counted
d[v, 0] = 1;
foreach (int i in gr[v])
{
if (i != par)
{
dfs(i, v);
// Count the pair of vertices at
// distance k
for (int j = 1; j <= k; j++)
ans += d[i, j - 1] * d[v, k - j];
// For all levels count vertices
for (int j = 1; j <= k; j++)
d[v, j] += d[i, j - 1];
}
}
}
// Driver code
public static void Main(String[] args)
{
n = 5;
k = 2;
for (int i = 0; i < N; i++)
gr[i] = new List<int>();
// Add edges
Add_edge(1, 2);
Add_edge(2, 3);
Add_edge(3, 4);
Add_edge(2, 5);
// Function call
dfs(1, 0);
// Required answer
Console.Write(ans);
}
}
// This code is contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
$N = 5005;
// To store vertices and value of k
$gr = array_fill(0, $N, array());
// To store number vertices
// at a level i
$d = array_fill(0, $N,
array_fill(0, 505, 0));
// To store the final answer
$ans = 0;
// Function to add an edge between
// two nodes
function Add_edge($x, $y)
{
global $gr;
array_push($gr[$x], $y);
array_push($gr[$y], $x);
}
// Function to find the number of distinct
// pairs of the vertices which have a
// distance of exactly k in a tree
function dfs($v, $par)
{
global $d, $ans, $k, $gr;
// At level zero vertex itself
// is counted
$d[$v][0] = 1;
foreach ($gr[$v] as &$i)
{
if ($i != $par)
{
dfs($i, $v);
// Count the pair of vertices
// at distance k
for ($j = 1; $j <= $k; $j++)
$ans += $d[$i][$j - 1] *
$d[$v][$k - $j];
// For all levels count vertices
for ($j = 1; $j <= $k; $j++)
$d[$v][$j] += $d[$i][$j - 1];
}
}
}
// Driver code
$n = 5;
$k = 2;
// Add edges
Add_edge(1, 2);
Add_edge(2, 3);
Add_edge(3, 4);
Add_edge(2, 5);
// Function call
dfs(1, 0);
// Required answer
echo $ans;
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
let N = 5005;
// To store vertices and value of k
let n, k;
let gr = new Array(N);
// To store number vertices at a level i
let d = new Array(N);
for(let i = 0 ; i < N; i++)
{
d[i] = new Array(505);
for(let j = 0; j < 505; j++)
{
d[i][j] = 0;
}
}
// To store the final answer
let ans = 0;
// Function to add an edge between two nodes
function Add_edge(x, y)
{
gr[x].push(y);
gr[y].push(x);
}
// Function to find the number of distinct
// pairs of the vertices which have a distance
// of exactly k in a tree
function dfs(v, par)
{
// At level zero vertex itself is counted
d[v][0] = 1;
for(let i = 0; i < gr[v].length; i++)
{
if (gr[v][i] != par)
{
dfs(gr[v][i], v);
// Count the pair of vertices at
// distance k
for(let j = 1; j <= k; j++)
ans += d[gr[v][i]][j - 1] * d[v][k - j];
// For all levels count vertices
for(let j = 1; j <= k; j++)
d[v][j] += d[gr[v][i]][j - 1];
}
}
}
// Driver code
n = 5;
k = 2;
for(let i = 0; i < N; i++)
gr[i] = [];
// Add edges
Add_edge(1, 2);
Add_edge(2, 3);
Add_edge(3, 4);
Add_edge(2, 5);
// Function call
dfs(1, 0);
// Required answer
document.write(ans);
// This code is contributed by unknown2108
</script>
Producción:
4
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N * 505)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA