Declaración del problema: dado un gráfico que representa una red de flujo donde cada borde tiene una capacidad. También dados dos vértices fuente ‘s’ y sumidero ‘t’ en el gráfico, encuentre el flujo máximo posible de s a t con las siguientes restricciones: El flujo en un borde no excede la capacidad dada del borde. … Continue reading «Algoritmo de Dinic para flujo máximo»
Dado un árbol no dirigido, necesitamos encontrar el camino más largo de este árbol donde un camino se define como una secuencia de Nodes. Ejemplo: Input : Below shown Tree using adjacency list representation: Output : 5 In below tree longest path is of length 5 from node 5 to node 7 Este problema es … Continue reading «Camino más largo en un árbol no dirigido»
Dada una array de tamaño N que consta de 0 y 1 , la tarea es encontrar el tiempo mínimo requerido para llenar toda la array con 1 . Cada 1 en un instante en la array, puede convertir todos los 0 en 1 en sus ocho celdas adyacentes, es decir, un 1 presente en … Continue reading «Tiempo mínimo requerido para llenar toda la array con 1»
Dado un gráfico no dirigido y un conjunto de vértices, encuentre todos los Nodes accesibles desde cada vértice presente en el conjunto dado. Considere el siguiente gráfico no dirigido con 2 componentes desconectados. arr[] = {1 , 2 , 5} Reachable nodes from 1 are 1, 2, 3, 4 Reachable nodes from 2 are … Continue reading «Encuentre todos los Nodes accesibles de cada Node presente en un conjunto dado»
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 árbol genérico que consiste en N Nodes valorados de 0 a (N – 1) donde P[i] th en la array P[] denota i th Nodes padre (indexación basada en 1) . Cada i -ésimo Node tiene un peso adjunto, dado en la array W[] . La tarea es encontrar un par de Nodes … Continue reading «Maximizar la diferencia entre un par de Nodes en un árbol enraizado dado, de modo que un Node sea el ancestro de otro»
Dada una pantalla 2D arr[][] donde cada arr[i][j] es un número entero que representa el color de ese píxel, también dada la ubicación de un píxel (X, Y) y un color C , la tarea es reemplazar el color del píxel dado y todos los píxeles adyacentes del mismo color con el color dado. Ejemplo: … Continue reading «Algoritmo de relleno de inundación – Part 1»
Dada una array binaria mat[][] de dimensiones NxM tal que 1 denota la isla y 0 denota el agua. La tarea es encontrar el número de islas cerradas en la array dada. Una isla cerrada se conoce como el grupo de 1 que está rodeado solo por 0 en los cuatro lados (excluyendo las diagonales). … Continue reading «Encuentre el número de islas cerradas en Matrix dada»
Dado un grafo conexo con N vértices. La tarea es seleccionar k (k debe ser menor o igual a n/2, no necesariamente mínimo) vértices del gráfico de manera que todos estos vértices seleccionados estén conectados a al menos uno de los vértices no seleccionados. En caso de múltiples respuestas imprima cualquiera de ellas. Ejemplos: Aporte … Continue reading «Encuentre K vértices en el gráfico que estén conectados a al menos uno de los vértices restantes»
Dada una string S de longitud N que consta de caracteres en minúsculas, la tarea es encontrar el costo mínimo para pasar del índice i al índice j . En cualquier índice k , el costo de saltar al índice k+1 y k-1 (sin salirse de los límites) es 1. Además, el costo de saltar a … Continue reading «Costo mínimo para pasar de un índice a otro en el String»