Dado un árbol binario que consta de N Nodes y dos números enteros R y K . Cada arista del árbol tiene un entero positivo asociado, dado en la forma {u, v, w} donde la arista (u, v) tiene un peso w . La tarea es calcular el número de Nodes S que tienen Bitwise XOR de todos los bordes en el camino desde la raíz R a S es igual a K .
Ejemplos:
Entrada: R = 1, K = 0, N = 7, Bordes[][] = {{1, 2, 3}, {1, 3, 1}, {2, 4, 3}, {2, 5, 4}, {3, 6, 1}, {3, 7, 2}}
Salida: 2
Explicación:
Representación del árbol binario dado:
El siguiente par de Nodes tiene un XOR bit a bit de aristas en la ruta que los conecta como K = 0:
Par 1: (1, 4) = (3 ^ 3) = 0
Par 2: (1, 6) = (1 ^ 1 ) = 0Entrada: R = 1, K = 0, N = 9, Bordes[][] = {{1, 2, 3}, {1, 3, 2}, {2, 4, 3}, {2, 5, 4}, {3, 6, 1}, {3, 7, 2}, {6, 8, 3}, {6, 9, 7}}
Salida: 3
Explicación:
La representación del árbol binario dado es la siguiente:
El siguiente par de Nodes tiene un XOR bit a bit de aristas en la ruta que los conecta como K = 0:
Par 1: (1, 4) = (3 ^ 3) = 0
Par 2: (1, 8) = (2 ^ 1 ^ 3) = 0
Par 3: (1, 7) = (2 ^ 2) = 0
Enfoque: el problema se puede resolver utilizando el enfoque de búsqueda primero en profundidad . Siga los pasos a continuación para resolver el problema:
- Inicialice la variable ans y xor con 0 para almacenar el número de pares y el xor actual de aristas.
- Atraviese el árbol dado utilizando la búsqueda en profundidad primero a partir del vértice raíz dado R .
- Para cada Node u , visite sus Nodes adyacentes.
- Para cada borde {u, v} , si xor es igual a K , incremente ans en 1 . De lo contrario, para el borde actual {u, v, w} , actualice xor como xor = (xor^w) donde ^ es el XOR bit a bit .
- Después de atravesar, imprima el valor almacenado en el contador y como el número de pares.
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;
// Initialize the adjacency list
// to represent the tree
vector<pair<int, int> > adj[100005];
// Marks visited / unvisited vertices
int visited[100005] = { 0 };
// Stores the required count of nodes
int ans = 0;
// DFS to visit each vertex
void dfs(int node, int xorr, int k)
{
// Mark the current node
// as visited
visited[node] = 1;
// Update the counter xor is K
if (node != 1 && xorr == k)
ans++;
// Visit adjacent nodes
for (auto x : adj[node]) {
if (!visited[x.first]) {
// Calculate Bitwise XOR of
// edges in the path
int xorr1 = xorr ^ x.second;
// Recursive call to dfs function
dfs(x.first, xorr1, k);
}
}
}
// Function to construct the tree and
// print required count of nodes
void countNodes(int N, int K, int R,
vector<vector<int> > edges)
{
// Add edges
for (int i = 0; i < N - 1; i++) {
int u = edges[i][0], v = edges[i][1],
w = edges[i][2];
adj[u].push_back({ v, w });
adj[v].push_back({ u, w });
}
dfs(R, 0, K);
// Print answer
cout << ans << "\n";
}
// Driver Code
int main()
{
// Given K and R
int K = 0, R = 1;
// Given edges
vector<vector<int> > edges
= { { 1, 2, 3 }, { 1, 3, 1 },
{ 2, 4, 3 }, { 2, 5, 4 },
{ 3, 6, 1 }, { 3, 7, 2 } };
// Number of vertices
int N = edges.size();
// Function call
countNodes(N, K, R, edges);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class GFG{
static class pair
{
int first, second;
public pair(int first,
int second)
{
this.first = first;
this.second = second;
}
}
// Initialize the adjacency list
// to represent the tree
static Vector<pair> []adj =
new Vector[100005];
// Marks visited / unvisited
// vertices
static int visited[] =
new int[100005];
// Stores the required
// count of nodes
static int ans = 0;
// DFS to visit each
// vertex
static void dfs(int node,
int xorr,
int k)
{
// Mark the current node
// as visited
visited[node] = 1;
// Update the counter
// xor is K
if (node != 1 &&
xorr == k)
ans++;
// Visit adjacent nodes
for (pair x : adj[node])
{
if (visited[x.first] != 1)
{
// Calculate Bitwise XOR of
// edges in the path
int xorr1 = xorr ^ x.second;
// Recursive call to dfs
// function
dfs(x.first, xorr1, k);
}
}
}
// Function to construct the tree and
// print required count of nodes
static void countNodes(int N, int K,
int R, int[][] edges)
{
// Add edges
for (int i = 0; i < N - 1; i++)
{
int u = edges[i][0],
v = edges[i][1],
w = edges[i][2];
adj[u].add(new pair(v, w ));
adj[v].add(new pair(u, w ));
}
dfs(R, 0, K);
// Print answer
System.out.print(ans + "\n");
}
// Driver Code
public static void main(String[] args)
{
// Given K and R
int K = 0, R = 1;
for (int i = 0; i < adj.length; i++)
adj[i] = new Vector<pair>();
// Given edges
int[][] edges = {{1, 2, 3},
{1, 3, 1},
{2, 4, 3},
{2, 5, 4},
{3, 6, 1},
{3, 7, 2}};
// Number of vertices
int N = edges.length;
// Function call
countNodes(N, K, R, edges);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Initialize the adjacency list # to represent the tree adj = [[] for i in range(100005)] # Marks visited / unvisited vertices visited = [0] * 100005 # Stores the required count of nodes ans = 0 # DFS to visit each vertex def dfs(node, xorr, k): global ans # Mark the current node # as visited visited[node] = 1 # Update the counter xor is K if (node != 1 and xorr == k): ans += 1 # Visit adjacent nodes for x in adj[node]: if (not visited[x[0]]): # Calculate Bitwise XOR of # edges in the path xorr1 = xorr ^ x[1] # Recursive call to dfs function dfs(x[0], xorr1, k) # Function to construct the tree and # prrequired count of nodes def countNodes(N, K, R, edges): # Add edges for i in range(N - 1): u = edges[i][0] v = edges[i][1] w = edges[i][2] adj[u].append([v, w]) adj[v].append([u, w]) dfs(R, 0, K) # Print answer print(ans) # Driver Code if __name__ == '__main__': # Given K and R K = 0 R = 1 # Given edges edges = [ [ 1, 2, 3 ],[ 1, 3, 1 ], [ 2, 4, 3 ],[ 2, 5, 4 ], [ 3, 6, 1 ],[ 3, 7, 2 ] ] # Number of vertices N = len(edges) # Function call countNodes(N, K, R, edges) # This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
public class pair
{
public int first,
second;
public pair(int first,
int second)
{
this.first = first;
this.second = second;
}
}
// Initialize the adjacency list
// to represent the tree
static List<pair> []adj =
new List<pair>[100005];
// Marks visited / unvisited
// vertices
static int []visited =
new int[100005];
// Stores the required
// count of nodes
static int ans = 0;
// DFS to visit each
// vertex
static void dfs(int node,
int xorr,
int k)
{
// Mark the current node
// as visited
visited[node] = 1;
// Update the counter
// xor is K
if (node != 1 &&
xorr == k)
ans++;
// Visit adjacent nodes
foreach (pair x in adj[node])
{
if (visited[x.first] != 1)
{
// Calculate Bitwise XOR of
// edges in the path
int xorr1 = xorr ^ x.second;
// Recursive call to dfs
// function
dfs(x.first, xorr1, k);
}
}
}
// Function to construct the tree and
// print required count of nodes
static void countNodes(int N, int K,
int R, int[,] edges)
{
// Add edges
for (int i = 0; i < N - 1; i++)
{
int u = edges[i,0];
int v = edges[i,1],
w = edges[i,2];
adj[u].Add(new pair(v, w ));
adj[v].Add(new pair(u, w ));
}
dfs(R, 0, K);
// Print answer
Console.Write(ans + "\n");
}
// Driver Code
public static void Main(String[] args)
{
// Given K and R
int K = 0, R = 1;
for (int i = 0; i < adj.Length; i++)
adj[i] = new List<pair>();
// Given edges
int[,] edges = {{1, 2, 3},
{1, 3, 1},
{2, 4, 3},
{2, 5, 4},
{3, 6, 1},
{3, 7, 2}};
// Number of vertices
int N = edges.GetLength(0);
// Function call
countNodes(N, K, R, edges);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Initialize the adjacency list
// to represent the tree
let adj = [];
for (let i = 0; i < 100005; i++) {
adj.push([])
}
// Marks visited / unvisited vertices
let visited = new Array(100005).fill(0);
// Stores the required count of nodes
let ans = 0;
// DFS to visit each vertex
function dfs(node, xorr, k) {
// Mark the current node
// as visited
visited[node] = 1;
// Update the counter xor is K
if (node != 1 && xorr == k)
ans++;
// Visit adjacent nodes
for (let x of adj[node]) {
if (!visited[x[0]]) {
// Calculate Bitwise XOR of
// edges in the path
let xorr1 = xorr ^ x[1];
// Recursive call to dfs function
dfs(x[0], xorr1, k);
}
}
}
// Function to construct the tree and
// print required count of nodes
function countNodes(N, K, R, edges) {
// Add edges
for (let i = 0; i < N - 1; i++) {
let u = edges[i][0], v = edges[i][1],
w = edges[i][2];
adj[u].push([v, w]);
adj[v].push([u, w]);
}
dfs(R, 0, K);
// Print answer
document.write(ans + "<br>");
}
// Driver Code
// Given K and R
let K = 0, R = 1;
// Given edges
let edges
= [[1, 2, 3], [1, 3, 1],
[2, 4, 3], [2, 5, 4],
[3, 6, 1], [3, 7, 2]];
// Number of vertices
let N = edges.length;
// Function call
countNodes(N, K, R, edges);
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
2
Complejidad temporal: O(N) donde N es el número de Nodes.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por prakhar_kochar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA