Un gráfico acíclico dirigido (DAG) es un gráfico que no contiene un ciclo y tiene bordes dirigidos. Nos dan un DAG, necesitamos clonarlo, es decir, crear otro gráfico que tenga una copia de sus vértices y aristas que los conectan. Ejemplos: Input : 0 – – – > 1 – – – -> 4 | … Continue reading «Clonar un gráfico acíclico dirigido»
Dado un gráfico dirigido y dos vértices ‘u’ y ‘v’ en él, cuente todos los recorridos posibles desde ‘u’ hasta ‘v’ con exactamente k aristas en el recorrido. El gráfico recibe una representación de array de adyacencia donde el valor de graph[i][j] como 1 indica que hay un borde desde el vértice i hasta el … Continue reading «Cuente todas las caminatas posibles desde un origen hasta un destino con exactamente k bordes»
Dada una array booleana 2D. La tarea es encontrar el número de islas distintas donde un grupo de 1 conectados (horizontal o verticalmente) forma una isla. Se considera que dos islas son distintas si y solo si una isla es igual a otra (no rotada ni reflejada). Ejemplos: Entrada: rejilla[][] = {{1, 1, 0, 0, … Continue reading «Encuentre el número de islas distintas en una array 2D»
Dado un gráfico no dirigido que consta de N vértices y M aristas, donde los valores de los Nodes están en el rango [1, N] y los vértices especificados por la array de color [] están coloreados, la tarea es encontrar el color mínimo de todos los vértices del dado. grafico. El costo de colorear … Continue reading «Minimice el costo de colorear todos los vértices de un gráfico no dirigido»
Dado un gráfico conexo no dirigido y no ponderado , encuentre un ciclo simple en ese gráfico (si existe). Ciclo Sencillo: Un ciclo simple es un ciclo en un gráfico sin vértices repetidos (excepto el vértice inicial y final). Básicamente, si un ciclo no se puede dividir en dos o más ciclos, entonces es un … Continue reading «Encuentre cualquier ciclo simple en un gráfico no ponderado no dirigido»
Dado un grafo no dirigido G con vértices numerados en el rango [1, N] y una array Aristas[][] que consta de M aristas, la tarea es verificar si todos los tripletes del grafo no dirigido satisfacen la propiedad transitiva o no. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” … Continue reading «Comprobar la propiedad transitiva en un gráfico no dirigido dado»
Dado un árbol y los pesos de todos los Nodes, la tarea es contar el número de Nodes cuyos pesos son pares, es decir, si el número de bits establecidos en ellos es par. Ejemplos: Aporte: Salida: 3 Peso Representación binaria Paridad 5 0101 Incluso 10 1010 Incluso 11 1011 Extraño 8 1000 Extraño 6 … Continue reading «Cuente los Nodes en el árbol dado cuyo peso es incluso paridad»
Hemos discutido el aplanamiento de una lista enlazada de varios niveles donde los Nodes tienen dos punteros hacia abajo y hacia adelante. En la publicación anterior, aplanamos la lista vinculada por niveles. Cómo aplanar una lista enlazada cuando siempre necesitamos procesar el puntero hacia abajo antes del siguiente en cada Node. Input: 1 – 2 … Continue reading «Aplanar una lista enlazada de varios niveles | Conjunto 2 (Profundidad sabia)»
Dado un árbol de N-arrays de N Nodes, con raíz en 1 , con bordes en la forma {u, v} , y una array de valores[] que consta de N enteros. Cada vértice i tiene un valor entero indicado por valores[i] . La tarea es encontrar la suma de subárbol más grande posible para cada … Continue reading «Mayor suma de subárboles para cada vértice del árbol N-ario dado»
Dado un gráfico de N Nodes y E aristas en forma de {U, V, W} tal que existe una arista entre U y V con peso W . Se le da un número entero K y fuente src y destino dst . La tarea es encontrar la ruta de costo más barata desde el origen … Continue reading «Ruta más corta de fuente única entre dos ciudades»