Hace poco recibí una pregunta en la entrevista de Amazon y quise saber las opiniones de desbordamiento de pila en el mismo.
La pregunta es que
Entrada: un grafo dirigido representado por lista de adyacencia
Salida requerida: ¿Este gráfico tiene un ciclo en un ciclo y, en caso afirmativo, cuáles son esos ciclos? Un ciclo en una condición de ciclo se define de la siguiente manera: hay 2 ciclos C1 y C2 en la gráfica y ambos comparten uno o más bordes, luego se llamarán ciclos en un ciclo.
Ejemplo de abajo:
En el gráfico anterior se puede ver que hay 2 cilindros.C-> D-> E-> F-> G-> H-> C y otro ciclo representado como H-> I-> J-> G-> H .. Podemos ver que estos 2 ciclos tienen los bordes G -> H como una ventaja compartida y, por lo tanto, podemos llamarlos ciclos en un ciclo.
So tha answer will be yes there are cycles in a cycles and
the cyles are C->D->E->F->G->H->C and H->I->J->G->H
Mi enfoque en una entrevista fue detectar todosLos ciclos (a través del recorrido DFS) y una vez detectados mantienen los bordes en un mapa hash. Luego, cuando se encuentra otro ciclo, los empujo nuevamente en hachís. Esto fue rechazado cortésmente y avanzó más en la entrevista sin seguir discutiendo. Entonces me di cuenta de que encontrar todos los ciclos es un problema difícil. Estoy confundido . ¿Puede alguien aclarar?
Respuestas
1 para la respuesta № 1- Encontrar todos los ciclos
- Compruebe si hay intersecciones no vacías entre los bordes de cada par de ciclos (si la intersección no está vacía, los dos ciclos son un ciclo en un ciclo)