Dado un árbol N-ario que consta de N Nodes con valores de 1 a N enraizados en 1, para todos los Nodes, imprima el número de ancestros que tienen un valor menor que el Node actual.
Ejemplo:
Entrada: A continuación se muestra el árbol dado:
1
/ \
4 5
/ / | \
6 3 2 7Salida: 0 1 1 1 1 2 2
Explicación:
Dado que el Node 1 es el Node raíz, no tiene ancestros.
Ancestros del Node 2: {1, 5}. El número de antepasados que tienen un valor menor que 2 es 1.
Antepasados del Node 3: {1, 5}. El número de antepasados que tienen un valor menor que 3 es 1.
Antepasados del Node 4: {1}. El número de antepasados que tienen un valor menor que 4 es 1.
Antepasados del Node 5: {1}. El número de antepasados que tienen un valor menor que 5 es 1.
Antepasados del Node 6: {1, 4}. El número de antepasados que tienen un valor menor que 6 es 2.
Antepasados del Node 7: {1, 5}. El número de antepasados que tienen un valor menor que 7 es 2Entrada: A continuación se muestra el árbol dado:
1
/ \
3 2
\
4Salida: 0 1 1 2
Explicación:
el Node 1 no tiene ancestros.
Ancestros del Node 2: {1}. El número de antepasados que tienen un valor menor que 2 es 1.
Antepasados del Node 3: {1}. El número de antepasados que tienen un valor menor que 3 es 1.
Enfoque de fuerza bruta: la idea es similar a lo que se menciona aquí: contar los ancestros con un valor más pequeño para cada Node de un árbol binario . La idea es usar DFS para cada Node y se puede extender fácilmente a un árbol N-ario .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque eficiente se basa en el concepto de Ordered_set , estructura de datos basada en políticas y DFS .
- Use un DFS de arriba hacia abajo para atravesar desde la raíz a todos los Nodes y use un conjunto ordenado para almacenar valores de todos los Nodes en la ruta desde la raíz hasta el Node actual.
- Cada vez que ingrese a un Node, antes de llamar a DFS en sus hijos, inserte el índice del Node en el conjunto ordenado y cada vez que salgamos del Node, borre el índice del Node del conjunto_ordenado. Esto asegura que order_set contendrá valores de todos los ancestros del Node actual.
- Dado que el conjunto ordenado brinda la funcionalidad de devolver una cantidad de valores más pequeños que x dados al encontrar el orden de x , para cada Node, siempre que ingrese al Node, simplemente encuentre el orden del índice del Node actual y obtenga la cantidad de valores más pequeños presentes en el conjunto_ordenado, es decir, el número de ancestros de menor valor para cada Node.
- Use un mapa para almacenar la cantidad de ancestros de menor valor para cada Node y utilícelo para imprimir la respuesta final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program for the above approach #include <bits/stdc++.h> // Common file #include <ext/pb_ds/assoc_container.hpp> // Including tree_order_statistics_node_update #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; // Declaring ordered_set typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // Map to store final ans for each node unordered_map<int, int> ans; // Function to add an edge // between nodes u and v void addEdge(vector<int> adj[], int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // Function to count the number of // ancestors with values smaller // than that of the current node void countSmallerAncestors( vector<int> adj[], int root, int par, ordered_set& ancestors) { // Map current node to // number of smaller valued ancestors ans[root] = ancestors.order_of_key(root); // Add current node to path ancestors.insert(root); for (int node : adj[root]) { // Avoid cycles if (node != par) { countSmallerAncestors( adj, node, root, ancestors); } } // Remove current node from path ancestors.erase(root); } // Driver Code int main() { // Number of nodes in graph int N = 7; // Initialize graph vector<int> adj[N + 1]; // Tree Formation addEdge(adj, 1, 5); addEdge(adj, 1, 4); addEdge(adj, 4, 6); addEdge(adj, 5, 3); addEdge(adj, 5, 2); addEdge(adj, 5, 7); // Ordered set to store values in path // from root to current node in dfs ordered_set ancestors; countSmallerAncestors(adj, 1, -1, ancestors); for (int i = 1; i <= N; i++) { cout << ans[i] << " "; } return 0; }
0 1 1 1 1 2 2
Complejidad temporal: O(N * log(N)).
Espacio Auxiliar: O(N).
Publicación traducida automáticamente
Artículo escrito por phantomcoder15 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA