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: … Continue reading «Recuento de ancestros con menor valor para cada Node de un árbol N-ario»
Dada una array de array 2-D [][] de tamaño M*N y un número entero K. Para cada aparición de K en la array[][] , reemplace K y todos los elementos adyacentes distintos de cero a su izquierda , derecha , arriba y abajo con 0 . El programa debe repetir el proceso hasta que todos … Continue reading «Minimice el conteo de pasos para hacer que todos los elementos de Matrix sean 0 al reemplazar los vecinos de K con 0»
El primer recorrido en profundidad (o búsqueda) de un gráfico es similar al primer recorrido en profundidad de un árbol. El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos (un Node puede visitarse dos veces). Para evitar procesar un Node más de una vez, use una array … Continue reading «Primera búsqueda en profundidad o DFS para un gráfico – Part 1»
Breadth-First Search: BFS, Breadth-First Search, es una técnica basada en vértices para encontrar la ruta más corta en el gráfico. Utiliza una estructura de datos de cola que sigue primero en entrar, primero en salir. En BFS, se selecciona un vértice a la vez cuando se visita y se marca, luego se visitan sus adyacentes … Continue reading «Diferencia entre BFS y DFS»
Dado un árbol binario que consta de N Nodes, la tarea es encontrar la suma de las profundidades de todos los Nodes del subárbol en un árbol binario dado. Ejemplos: Aporte: Salida: 26 Explicación: Los Nodes hoja que tienen el valor 8, 9, 5, 6 y 7 tienen la suma de las profundidades del subárbol … Continue reading «Suma de profundidades de subárbol para cada Node de un árbol binario dado»
Dado un gráfico g no dirigido , la tarea es imprimir el número de componentes conectados en el gráfico. Ejemplos: Aporte: Salida: 3 Hay tres componentes conectados: 1 – 5, 0 – 2 – 4 y 3 Acercarse: DFS visita todos los vértices conectados del vértice dado. Al iterar sobre todos los vértices, cada vez … Continue reading «Programa para contar Número de componentes conectados en un gráfico no dirigido»
Los gráficos se pueden usar para problemas aparentemente inconexos. Diga el problema de las tarjetas que tienen números en ambos lados e intente crear una secuencia continua de números usando un lado. Este problema genera problemas sobre cómo dividir un gráfico en subconjuntos conectados con ciclos y subconjuntos conectados sin ciclos. Existen algoritmos conocidos para … Continue reading «División de gráficos no dirigida y su aplicación para pares de números»
Dada una escala de ponderación y una array de diferentes pesos positivos donde tenemos un suministro infinito de cada peso. Nuestra tarea es poner pesos en los platillos de la balanza izquierda y derecha uno por uno de tal manera que los platillos se muevan hacia el lado donde se coloca el peso, es decir, … Continue reading «Mover la escala de ponderación alternativa bajo las restricciones dadas»
¿Qué es un Vértice Madre? Un vértice madre en un grafo G = (V, E) es un vértice v tal que se puede llegar a todos los demás vértices en G por un camino desde v. Ejemplo: Input : Below Graph Output : 5 Puede haber más de un vértice madre en un gráfico. Necesitamos … Continue reading «Encuentra un vértice madre en un gráfico»
Dado un grafo acíclico no dirigido que tiene N Nodes y M aristas, la tarea es encontrar el tamaño del árbol más grande del bosque formado por el grafo. Un bosque es una colección de árboles disjuntos. En otras palabras, también podemos decir que forest es una colección de un gráfico acíclico que no está … Continue reading «Tamaño de los árboles más grandes en un bosque formado por el gráfico dado»