El primer recorrido en profundidad (o búsqueda) de un gráfico es similar al primer recorrido en profundidad (DFS) de un árbol . El único inconveniente aquí es que, a diferencia de los árboles, los gráficos pueden contener ciclos, por lo que un Node puede visitarse dos veces. Para evitar procesar un Node más de una … Continue reading «Profundidad iterativa Primer recorrido del gráfico»
Dados dos enteros ‘n’ y ‘m’, encuentre todos los números de paso en el rango [n, m]. Un número se llama número de paso si todos los dígitos adyacentes tienen una diferencia absoluta de 1. 321 es un número de paso mientras que 421 no lo es. Ejemplos: Input : n = 0, m = … Continue reading «Números escalonados»
Escribe una función que devuelva verdadero si un gráfico no dirigido dado es un árbol y falso en caso contrario. Por ejemplo, el siguiente gráfico es un árbol. C++ // A C++ Program to check whether a graph is tree or not #include<iostream> #include <list> #include <limits.h> using namespace std; // Class for an … Continue reading «Comprobar si un gráfico dado es árbol o no»
Dado un gráfico con N Nodes numerados del 1 al N y M aristas y una array de números del 1 al N. Compruebe si es posible obtener alguna permutación de la array aplicando DFS (Depth First Traversal) en el gráfico dado. Requisitos previos: DFS | Mapa en CPP Ejemplos: Input: N = 3, M … Continue reading «Compruebe si la permutación dada es un DFS de gráfico válido»
Dado un árbol binario que consta de N Nodes que no tienen valores y un número entero X , que representa el valor del Node raíz, la tarea es encontrar la suma mínima de todos los valores de los Nodes del árbol dado tal que el valor de cada el Node debe ser el valor … Continue reading «Minimice la suma de los valores de los Nodes llenando el árbol vacío dado de modo que cada Node sea GCD de sus hijos»
Dada una array binaria mat[][] que representa la representación de array de adyacencia de un gráfico , donde mat[i][j] como 1 representa que hay un borde entre los vértices i y j y un vértice V , la tarea es encontrar el camino más largo desde cualquier Node al vértice X tal que cada vértice … Continue reading «Longitud del camino más largo que termina en el vértice V en un gráfico»
Dado un árbol con N Nodes numerados de 1 a N y N – 1 arista y array colors[] donde colors[i] denota el color del i -th Node. La tarea es encontrar un Node tal que cada árbol vecino conectado a este Node esté formado por Nodes del mismo color. Si no existe tal Node, … Continue reading «Imprimir Node cuyo árbol vecino tiene todos los Nodes del mismo color»
Dada una string de Markov G, tenemos la probabilidad de alcanzar el estado F en el tiempo t = T si comenzamos desde el estado S en el tiempo t = 0. Una string de Markov es un proceso aleatorio que consta de varios estados y las probabilidades de moverse de un estado a otro. … Continue reading «Encuentre la probabilidad de un estado en un momento dado en una string de Markov | Serie 1»
Dado un árbol N-ario con algún color asociado con cada Node y consultas Q. Cada consulta contiene dos enteros A y X . La tarea es contar todos los colores distintos en un subárbol con raíz en A , que tenga una frecuencia de colores mayor o igual a X en ese subárbol. Ejemplos: Entrada: … Continue reading «Recuento de colores distintos en un subárbol de un árbol de colores con una frecuencia mínima dada para consultas Q»
Dado un grafo dirigido G con N vértices y M aristas . La tarea es encontrar la longitud del camino dirigido más largo en Graph. Nota: La longitud de un camino dirigido es el número de aristas que tiene. Ejemplos: Entrada: N = 4, M = 5 Salida: 3 El camino dirigido 1->3->2->4 Entrada: N = … Continue reading «Camino más largo en un gráfico acíclico dirigido | Programación dinámica»