Dada una array Arr de N enteros que representan los Nodes de un gráfico. Los bordes se definen entre aquellos pares cuyo AND bit a bit no es igual a cero . La tarea es encontrar si existe un ciclo de longitud 3 o no en el gráfico.
Ejemplos:
Entrada: Arr[] = {26, 33, 35, 40, 50}
Salida: Sí
Existe un ciclo entre 26, 33 y 50.
Entrada: Arrr[] = {17, 142, 243, 300}
Salida: No
Enfoque ingenuo:
ejecute un bucle anidado y verifique para cada par si existe un borde entre ellos (si su valor AND bit a bit no es cero). Por lo tanto, formamos el gráfico completo y verificamos si existe un ciclo en este gráfico utilizando cualquiera de los métodos de detección de ciclos .
Enfoque eficiente:
- Un ciclo se forma uniendo al menos 3 aristas.
- La idea es hacer una array 2D donde la i-ésima fila almacene el valor binario de Arr[i].
- A continuación, realice un bucle en forma de columna y verifique si existe una columna donde el número de 1 es al menos 3.
- Si es así, implica que existe un ciclo en el gráfico.
- Si no existe tal columna, implica que no hay ciclo en el gráfico.
Arr[] = {26, 33, 35, 40, 50}
La array 2D es la siguiente
bi = [
[0 1 0 1 1 0 0 0],
[1 0 0 0 0 1 0 0],
[1 1 0 0 0 1 0 0],
[0 0 0 1 0 1 0 0],
[0 1 0 0 1 1 0 0],
]
bi[0][1], bi[2][1] y bi[4] [1] son iguales a 1. Esto implica que el valor AND bit a bit de los siguientes pares (Arr[0], Arr[2]), (Arr[2], Arr[4]), (Arr[0], Arr[ 4]) son distintos de cero. Estos 3 bordes forman un ciclo.
A continuación se muestra la implementación del enfoque anterior:
Bloque de código
Yes