Categoría: Topological Sorting

Tiempo mínimo que tarda cada trabajo en completarse dado por un gráfico acíclico dirigido

Posted on by Rudeus Greyrat

Dado un gráfico acíclico dirigido que tiene V vértices y E aristas, donde cada arista {U, V} representa los trabajos U y V , de modo que el trabajo V solo puede iniciarse después de completar el trabajo U. La tarea es determinar el tiempo mínimo que tarda cada trabajo en completarse, donde cada trabajo … Continue reading «Tiempo mínimo que tarda cada trabajo en completarse dado por un gráfico acíclico dirigido»

Encuentra al ganador del partido | Consultas Múltiples

Posted on by Rudeus Greyrat

Dada una array de pares arr de tamaño N que representa una situación de juego en la que el primer jugador gana contra el segundo jugador. Dadas múltiples consultas, cada consulta contiene dos números, la tarea es determinar cuál de ellos ganará si compiten entre sí. NOTA:   Si A gana sobre B y B gana … Continue reading «Encuentra al ganador del partido | Consultas Múltiples»

Bordes máximos que se pueden agregar a DAG para que siga siendo DAG

Posted on by Rudeus Greyrat

Se nos da un DAG, necesitamos encontrar el número máximo de aristas que se pueden agregar a este DAG, después de lo cual el nuevo gráfico sigue siendo un DAG, lo que significa que el gráfico reformado debe tener la cantidad máxima de aristas, agregar incluso un solo borde creará un ciclo en el gráfico. … Continue reading «Bordes máximos que se pueden agregar a DAG para que siga siendo DAG»

Minimice los colores para pintar el gráfico de modo que ninguna ruta tenga el mismo color

Posted on by Rudeus Greyrat

Ejemplos: Entrada:  N = 5, M = 6, mat = {{1, 3}, {2, 3}, {3, 4}, {1, 4}, {2, 5}, {3, 5}} Salida : 3 Explicación: Los Nodes del gráfico se pueden colorear como se muestra a continuación y esa es la cantidad mínima de colores posible.  Ejemplo 1 Entrada: N = 3, M = … Continue reading «Minimice los colores para pintar el gráfico de modo que ninguna ruta tenga el mismo color»

Camino más largo entre cualquier par de vértices

Posted on by Rudeus Greyrat

Nos dan un mapa de ciudades conectadas entre sí a través de líneas de cable de modo que no hay ciclo entre dos ciudades. Necesitamos encontrar la longitud máxima de cable entre dos ciudades para un mapa de ciudad dado.  Input : n = 6 1 2 3 // Cable length from 1 to 2 … Continue reading «Camino más largo entre cualquier par de vértices»

Genere la permutación lexicográficamente más pequeña de 1 a N donde los elementos siguen una relación dada

Posted on by Rudeus Greyrat

Dado un número entero N y una array arr[] de M pares de tipo ( A i , B i ), la tarea es generar la permutación lexicográficamente más pequeña posible de 1 a N tal que cada A i ocurra antes que cada B i . Ejemplos: Entrada: N = 4, arr[] = { … Continue reading «Genere la permutación lexicográficamente más pequeña de 1 a N donde los elementos siguen una relación dada»

Asigne direcciones a los bordes para que el gráfico dirigido permanezca acíclico

Posted on by Rudeus Greyrat

Dado un gráfico con aristas dirigidas y no dirigidas. Se da que las aristas dirigidas no forman ciclo. ¿Cómo asignar direcciones a los bordes no dirigidos para que el gráfico (con todos los bordes dirigidos) permanezca acíclico incluso después de la asignación?  Por ejemplo, en el siguiente gráfico, los bordes azules no tienen direcciones.    … Continue reading «Asigne direcciones a los bordes para que el gráfico dirigido permanezca acíclico»

Compruebe si las arrays dadas tienen una supersecuencia común única más corta

Posted on by Rudeus Greyrat

Dada una array 2D arr[][] de tamaño N*M que denota N arrays, cada una de tamaño M . La tarea es verificar si todas estas arrays tienen una supersecuencia común única. Ejemplos: Entrada : N = 2, M = 2, arr[][] = { { 1, 2 }, {1, 3 } } Salida : Falso Explicación … Continue reading «Compruebe si las arrays dadas tienen una supersecuencia común única más corta»

Todos los tipos topológicos de un gráfico acíclico dirigido

Posted on by Rudeus Greyrat

La ordenación topológica para un gráfico cíclico dirigido ( DAG ) es una ordenación lineal de vértices tal que para cada arista dirigida uv, el vértice u viene antes que v en la ordenación. La clasificación topológica de un gráfico no es posible si el gráfico no es un DAG. Dado un DAG, imprima todos … Continue reading «Todos los tipos topológicos de un gráfico acíclico dirigido»