Categoría: union-find

Algoritmo de búsqueda de unión | (Unión por rango y búsqueda por compresión de ruta optimizada)

Posted on by Rudeus Greyrat

Comprueba si un gráfico dado contiene un ciclo o no. Ejemplo:  Input: Output: Graph contains Cycle. Input: Output: Graph does not contain Cycle. Prerrequisitos: conjunto disjunto (o unión-búsqueda) , unión por rango y compresión de ruta Ya hemos discutido unión-búsqueda para detectar ciclos . Aquí discutimos la búsqueda por compresión de ruta, donde se modifica … Continue reading «Algoritmo de búsqueda de unión | (Unión por rango y búsqueda por compresión de ruta optimizada)»

Consultas para verificar si los vértices X e Y están en el mismo Componente Conectado de un Gráfico No Dirigido

Posted on by Rudeus Greyrat

Dado un grafo no dirigido que consta de N vértices y M aristas y consultas Q[][] del tipo {X, Y} , la tarea es comprobar si los vértices X e Y están en la misma componente conexa del Gráfico. Ejemplos: Entrada: Q[][] = {{1, 5}, {3, 2}, {5, 2}}  Gráfico:   1-3-4 2 | 5 Salida: … Continue reading «Consultas para verificar si los vértices X e Y están en el mismo Componente Conectado de un Gráfico No Dirigido»

Problema de secuenciación de trabajos | Conjunto 2 (usando conjunto disjunto)

Posted on by Rudeus Greyrat

Dado un conjunto de n trabajos donde cada trabajo i tiene una fecha límite di >=1 y una ganancia pi>=0. Solo se puede programar un trabajo a la vez. Cada trabajo tarda 1 unidad de tiempo en completarse. Obtenemos la ganancia si y solo si el trabajo se completa antes de su fecha límite. La … Continue reading «Problema de secuenciación de trabajos | Conjunto 2 (usando conjunto disjunto)»

Compruebe si los intervalos dados se pueden hacer que no se superpongan sumando/restando algunas X

Posted on by Rudeus Greyrat

Dada una array arr[] que contiene N intervalos, la tarea es verificar si los intervalos se pueden sumar o restar por X después de lo cual no hay intervalos superpuestos. Sea X cualquier número real. Ejemplos:  Entrada: arr[] = {[1, 3], [2, 4], [4, 5], [5, 6]}  Salida: SI  Explicación:  Podemos sumar X = 1000  … Continue reading «Compruebe si los intervalos dados se pueden hacer que no se superpongan sumando/restando algunas X»

Consultas para encontrar el recuento de celdas no vacías conectadas en una array con actualizaciones

Posted on by Rudeus Greyrat

Dada una array booleana mat[][] que consta de N filas y M columnas, inicialmente rellenas con 0 (celdas vacías), un número entero K y consultas Q[][] del tipo {X, Y}, la tarea es para reemplazar mat[X][Y] = 1 (celdas no vacías) y contar el número de celdas no vacías conectadas de la array dada. Ejemplos:  … Continue reading «Consultas para encontrar el recuento de celdas no vacías conectadas en una array con actualizaciones»

Encuentre el tamaño máximo del componente después de agregar cada borde al gráfico

Posted on by Rudeus Greyrat

Dada una array arr[][] que contiene los bordes de un gráfico que se usará para construir un gráfico no dirigido G con N Nodes, la tarea es encontrar el tamaño máximo del componente en el gráfico después de agregar cada borde mientras se construye el gráfico. Ejemplos:  Entrada: N = 4, arr[][] = {{1, 2}, … Continue reading «Encuentre el tamaño máximo del componente después de agregar cada borde al gráfico»