Dado un árbol como un conjunto de aristas tal que cada Node tiene un valor único. También se nos da un valor k, la tarea es contar las rutas únicas en el árbol de modo que cada ruta tenga un valor mayor que K. Se dice que un valor de ruta es > K si cada borde que contribuye a la ruta conecta dos Nodes ambos tienen valores > K .
Ejemplos:
Aporte:
Salida: 9
Planteamiento: La idea es no formar el árbol con todas las aristas dadas. Solo añadimos una arista si cumple la condición de > k. En este caso, se formarán varios árboles. Mientras formamos los diferentes árboles, solo agregaremos el borde en el árbol si ambos valores de Node son mayores que K. Después de esto, se crearán varios números de árboles. Ejecute un DFS para cada Node que al final atraviesa el árbol completo con el que está conectado el Node y cuente la cantidad de Nodes en cada árbol. El número de rutas únicas para cada árbol que tiene X número de Nodes es X * (X – 1) / 2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the number of nodes
// in the tree using DFS
int dfs(int node, int parent, list<int>* adj, bool vis[])
{
// Base case
int ans = 1;
// Mark as visited
vis[node] = true;
// Traverse for all children
for (auto it : adj[node]) {
// If not equal to parent
if (it != parent)
ans += dfs(it, node, adj, vis);
}
return ans;
}
// Function that returns the count of
// unique paths
int countPaths(list<int>* adj, int k, int maxn)
{
// An array that marks if the node
// is visited or not
bool vis[maxn + 1];
int ans = 0;
// Initially marked as false
memset(vis, false, sizeof vis);
// Traverse till max value of node
for (int i = 1; i <= maxn; i++) {
// If not visited
if (!vis[i]) {
// Get the number of nodes in that
// tree
int numNodes = dfs(i, 0, adj, vis);
// Total unique paths in the current
// tree where numNodes is the total
// nodes in the tree
ans += numNodes * (numNodes - 1) / 2;
}
}
return ans;
}
// Function to add edges to tree if value
// is less than K
void addEdge(list<int>* adj, int u, int v, int k)
{
if (u > k && v > k) {
adj[u].push_back(v);
adj[v].push_back(u);
}
}
// Driver code
int main()
{
int maxn = 12;
list<int>* adj = new list<int>[maxn + 1];
int k = 3;
// Create undirected edges
addEdge(adj, 2, 11, k);
addEdge(adj, 2, 6, k);
addEdge(adj, 5, 11, k);
addEdge(adj, 5, 10, k);
addEdge(adj, 5, 12, k);
addEdge(adj, 6, 7, k);
addEdge(adj, 6, 8, k);
cout << countPaths(adj, k, maxn);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to count the number of nodes
// in the tree using DFS
static int dfs(int node, int parent,
Vector<Integer>[] adj, boolean[] vis)
{
// Base case
int ans = 1;
// Mark as visited
vis[node] = true;
// Traverse for all children
for (Integer it : adj[node])
{
// If not equal to parent
if (it != parent)
ans += dfs(it, node, adj, vis);
}
return ans;
}
// Function that returns the count of
// unique paths
static int countPaths(Vector<Integer>[] adj,
int k, int maxn)
{
// An array that marks if the node
// is visited or not
boolean[] vis = new boolean[maxn + 1];
int ans = 0;
// Initially marked as false
Arrays.fill(vis, false);
// Traverse till max value of node
for (int i = 1; i <= maxn; i++)
{
// If not visited
if (!vis[i])
{
// Get the number of nodes in that
// tree
int numNodes = dfs(i, 0, adj, vis);
// Total unique paths in the current
// tree where numNodes is the total
// nodes in the tree
ans += numNodes * (numNodes - 1) / 2;
}
}
return ans;
}
// Function to add edges to tree if value
// is less than K
static void addEdge(Vector<Integer>[] adj,
int u, int v, int k)
{
if (u > k && v > k) {
adj[u].add(v);
adj[v].add(u);
}
}
// Driver Code
public static void main(String[] args)
{
int maxn = 12;
@SuppressWarnings("unchecked")
Vector<Integer>[] adj = new Vector[maxn + 1];
for (int i = 0; i < maxn + 1; i++)
{
adj[i] = new Vector<>();
}
int k = 3;
// Create undirected edges
addEdge(adj, 2, 11, k);
addEdge(adj, 2, 6, k);
addEdge(adj, 5, 11, k);
addEdge(adj, 5, 10, k);
addEdge(adj, 5, 12, k);
addEdge(adj, 6, 7, k);
addEdge(adj, 6, 8, k);
System.out.println(countPaths(adj, k, maxn));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach # Function to count the number of # nodes in the tree using DFS def dfs(node, parent, adj, vis): # Base case ans = 1 # Mark as visited vis[node] = True # Traverse for all children for it in adj[node]: # If not equal to parent if it != parent: ans += dfs(it, node, adj, vis) return ans # Function that returns the # count of unique paths def countPaths(adj, k, maxn): # An array that marks if # the node is visited or not vis = [False] * (maxn + 1) ans = 0 # Traverse till max value of node for i in range(1, maxn+1): # If not visited if not vis[i]: # Get the number of # nodes in that tree numNodes = dfs(i, 0, adj, vis) # Total unique paths in the current # tree where numNodes is the total # nodes in the tree ans += numNodes * (numNodes - 1) // 2 return ans # Function to add edges to # tree if value is less than K def addEdge(adj, u, v, k): if u > k and v > k: adj[u].append(v) adj[v].append(u) # Driver code if __name__ == "__main__": maxn = 12 adj = [[] for i in range(maxn + 1)] k = 3 # Create undirected edges addEdge(adj, 2, 11, k) addEdge(adj, 2, 6, k) addEdge(adj, 5, 11, k) addEdge(adj, 5, 10, k) addEdge(adj, 5, 12, k) addEdge(adj, 6, 7, k) addEdge(adj, 6, 8, k) print(countPaths(adj, k, maxn)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG{
// Function to count the number of nodes
// in the tree using DFS
static int dfs(int node, int parent,
List<int>[] adj, bool[] vis)
{
// Base case
int ans = 1;
// Mark as visited
vis[node] = true;
// Traverse for all children
foreach(int it in adj[node])
{
// If not equal to parent
if (it != parent)
ans += dfs(it, node, adj, vis);
}
return ans;
}
// Function that returns the count of
// unique paths
static int countPaths(List<int>[] adj,
int k, int maxn)
{
// An array that marks if the node
// is visited or not
bool[] vis = new bool[maxn + 1];
int ans = 0;
// Traverse till max value of node
for(int i = 1; i <= maxn; i++)
{
// If not visited
if (!vis[i])
{
// Get the number of nodes in that
// tree
int numNodes = dfs(i, 0, adj, vis);
// Total unique paths in the current
// tree where numNodes is the total
// nodes in the tree
ans += numNodes * (numNodes - 1) / 2;
}
}
return ans;
}
// Function to add edges to tree if value
// is less than K
static void addEdge(List<int>[] adj,
int u, int v, int k)
{
if (u > k && v > k)
{
adj[u].Add(v);
adj[v].Add(u);
}
}
// Driver Code
public static void Main(String[] args)
{
int maxn = 12;
List<int>[] adj = new List<int>[maxn + 1];
for(int i = 0; i < maxn + 1; i++)
{
adj[i] = new List<int>();
}
int k = 3;
// Create undirected edges
addEdge(adj, 2, 11, k);
addEdge(adj, 2, 6, k);
addEdge(adj, 5, 11, k);
addEdge(adj, 5, 10, k);
addEdge(adj, 5, 12, k);
addEdge(adj, 6, 7, k);
addEdge(adj, 6, 8, k);
Console.WriteLine(countPaths(adj, k, maxn));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript implementation of the approach
// Function to count the number of nodes
// in the tree using DFS
function dfs(node, parent, adj, vis)
{
// Base case
let ans = 1;
// Mark as visited
vis[node] = true;
// Traverse for all children
for (let it = 0; it < adj[node].length; it++)
{
// If not equal to parent
if (adj[node][it] != parent)
ans += dfs(adj[node][it], node, adj, vis);
}
return ans;
}
// Function that returns the count of
// unique paths
function countPaths(adj, k, maxn)
{
// An array that marks if the node
// is visited or not
let vis = new Array(maxn + 1);
let ans = 0;
// Initially marked as false
vis.fill(false);
// Traverse till max value of node
for (let i = 1; i <= maxn; i++)
{
// If not visited
if (!vis[i])
{
// Get the number of nodes in that
// tree
let numNodes = dfs(i, 0, adj, vis);
// Total unique paths in the current
// tree where numNodes is the total
// nodes in the tree
ans += numNodes * (numNodes - 1) / 2;
}
}
return ans;
}
// Function to add edges to tree if value
// is less than K
function addEdge(adj, u, v, k)
{
if (u > k && v > k) {
adj[u].push(v);
adj[v].push(u);
}
}
let maxn = 12;
let adj = new Array(maxn + 1);
for (let i = 0; i < maxn + 1; i++)
{
adj[i] = [];
}
let k = 3;
// Create undirected edges
addEdge(adj, 2, 11, k);
addEdge(adj, 2, 6, k);
addEdge(adj, 5, 11, k);
addEdge(adj, 5, 10, k);
addEdge(adj, 5, 12, k);
addEdge(adj, 6, 7, k);
addEdge(adj, 6, 8, k);
document.write(countPaths(adj, k, maxn));
</script>
Producción:
9
Complejidad de tiempo: O (N), ya que estamos usando la recursividad para atravesar N veces. Donde N es el número total de Nodes.
Espacio auxiliar: O(N), ya que estamos usando espacio extra para el arreglo visitado. Donde N es el número total de Nodes.