Dado un árbol y los pesos de todos los Nodes, la tarea es contar el número de Nodes cuyos pesos son pares, es decir, si el número de bits establecidos en ellos es par.
Ejemplos:
Aporte:
Salida: 3
Peso Representación binaria Paridad 5 0101 Incluso 10 1010 Incluso 11 1011 Extraño 8 1000 Extraño 6 0110 Incluso
Enfoque: Realice dfs en el árbol y para cada Node, verifique si su peso es paritario o no. Si es así, entonces incremente el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; int ans = 0; vector<int> graph[100]; vector<int> weight(100); // Function that returns true if count // of set bits in x is even bool isEvenParity(int x) { // parity will store the // count of set bits int parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false; } // Function to perform dfs void dfs(int node, int parent) { // If weight of the current // node has even parity if (isEvenParity(weight[node])) ans += 1; for (int to : graph[node]) { if (to == parent) continue; dfs(to, node); } } // Driver code int main() { // Weights of the node weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; // Edges of the tree graph[1].push_back(2); graph[2].push_back(3); graph[2].push_back(4); graph[1].push_back(5); dfs(1, 1); cout << ans; return 0; }
Java
// Java implementation of the approach import java.util.*; class GFG { static int ans = 0; static Vector<Vector<Integer>> graph = new Vector<Vector<Integer>>(); static Vector<Integer> weight = new Vector<Integer>(); // Function that returns true if count // of set bits in x is even static boolean isEvenParity(int x) { // parity will store the // count of set bits int parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false; } // Function to perform dfs static void dfs(int node, int parent) { // If weight of the current // node has even parity if (isEvenParity(weight.get(node) )) ans += 1; for (int i = 0; i < graph.get(node).size(); i++) { if (graph.get(node).get(i) == parent) continue; dfs(graph.get(node).get(i) , node); } } // Driver code public static void main(String args[]) { // Weights of the node weight.add( 0); weight.add( 5); weight.add( 10);; weight.add( 11);; weight.add( 8); weight.add( 6); for(int i=0;i<100;i++) graph.add(new Vector<Integer>()); // Edges of the tree graph.get(1).add(2); graph.get(2).add(3); graph.get(2).add(4); graph.get(1).add(5); dfs(1, 1); System.out.println( ans ); } } // This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach ans = 0 graph = [[] for i in range(100)] weight = [0]*100 # Function that returns True if count # of set bits in x is even def isEvenParity(x): # parity will store the # count of set bits parity = 0 while (x != 0): x = x & (x - 1) parity += 1 if (parity % 2 == 0): return True else: return False # Function to perform dfs def dfs(node, parent): global ans # If weight of the current # node has even parity if (isEvenParity(weight[node])): ans += 1 for to in graph[node]: if (to == parent): continue dfs(to, node) # Driver code # Weights of the node weight[1] = 5 weight[2] = 10 weight[3] = 11 weight[4] = 8 weight[5] = 6 # Edges of the tree graph[1].append(2) graph[2].append(3) graph[2].append(4) graph[1].append(5) dfs(1, 1) print(ans) # This code is contributed by SHUBHAMSINGH10
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { static int ans = 0; static List<List<int>> graph = new List<List<int>>(); static List<int> weight = new List<int>(); // Function that returns true if count // of set bits in x is even static bool isEvenParity(int x) { // parity will store the // count of set bits int parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false; } // Function to perform dfs static void dfs(int node, int parent) { // If weight of the current // node has even parity if (isEvenParity(weight[node])) ans += 1; for (int i = 0; i < graph[node].Count; i++) { if (graph[node][i] == parent) continue; dfs(graph[node][i] , node); } } // Driver code static void Main() { // Weights of the node weight.Add(0); weight.Add(5); weight.Add(10); weight.Add(11); weight.Add(8); weight.Add(6); for(int i = 0; i < 100; i++) graph.Add(new List<int>()); // Edges of the tree graph[1].Add(2); graph[2].Add(3); graph[2].Add(4); graph[1].Add(5); dfs(1, 1); Console.WriteLine( ans ); } } // This code is contributed by mits
Javascript
<script> // Javascript implementation of the approach let ans = 0; let graph = new Array(100); let weight = new Array(100); for(let i = 0; i < 100; i++) { graph[i] = []; weight[i] = 0; } // Function that returns true if count // of set bits in x is even function isEvenParity(x) { // parity will store the // count of set bits let parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false; } // Function to perform dfs function dfs(node, parent) { // If weight of the current // node has even parity if (isEvenParity(weight[node])) ans += 1; for(let to=0;to<graph[node].length;to++) { if(graph[node][to] == parent) continue dfs(graph[node][to], node); } } // Driver code // Weights of the node weight[1] = 5; weight[2] = 10; weight[3] = 11; weight[4] = 8; weight[5] = 6; // Edges of the tree graph[1].push(2); graph[2].push(3); graph[2].push(4); graph[1].push(5); dfs(1, 1); document.write(ans); // This code is contributed by Dharanendra L V. </script>
Producción:
3
Análisis de Complejidad:
- Complejidad temporal: O(N).
En DFS, cada Node del árbol se procesa una vez y, por lo tanto, la complejidad debida al DFS es O(N) para N Nodes en el árbol. Por lo tanto, la complejidad del tiempo es O(N). - Espacio Auxiliar: O(1).
No se requiere ningún espacio adicional, por lo que la complejidad del espacio es constante.
Publicación traducida automáticamente
Artículo escrito por mohit kumar 29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA