Entrevista técnica de código: Encontrar todas las conexiones críticas en una red

Prompt y contexto aplicable

Se te dan n nodos etiquetados de 0 a n - 1 y un arreglo connections, donde cada par [u, v] es una arista no dirigida. El grafo es conexo y simple: no tiene bucles ni aristas repetidas. Devuelve cada conexión crítica, es decir, cada arista cuya eliminación desconecta el grafo. La respuesta puede estar en cualquier orden, y cualquier orden de los extremos es aceptable.

Asume 2 <= n <= 100000 y n - 1 <= connections.length <= 100000. Por ejemplo:

n = 4
connections = [[0, 1], [1, 2], [2, 0], [1, 3]]
output = [[1, 3]]

Las primeras tres aristas forman un ciclo, por lo que eliminar cualquiera de ellas deja una ruta alternativa. El nodo 3 solo tiene la arista [1, 3]; eliminarla separa al nodo 3. En la terminología de grafos, una conexión crítica es un puente (bridge).

Esta es una pregunta de código sobre invariantes de grafos. Difiere del artículo existente de Union-Find, que mantiene componentes conexas a medida que se agregan aristas; difiere del ordenamiento topológico, que ordena un grafo acíclico dirigido; y difiere de Dijkstra, que optimiza la longitud de caminos ponderados. Aquí la salida depende de cómo cambia la conectividad tras eliminar cada arista no dirigida.

Qué evalúa el entrevistador

La primera señal es si el candidato descarta el enfoque obvio de búsqueda repetida a la escala planteada. Eliminar una arista y ejecutar BFS o DFS responde una consulta correctamente, pero repetir eso para las m aristas cuesta un tiempo de O(m(n + m)). Con 100 000 aristas, un recorrido lineal por arista no es viable.

La segunda señal es un invariante de low-link preciso. El tiempo de descubrimiento en DFS tin[u] registra cuándo se visita u por primera vez. low[u] es el tiempo de descubrimiento más temprano alcanzable desde el subárbol DFS de u descendiendo por aristas del árbol y luego utilizando a lo sumo una arista que no pertenezca al árbol. Para una arista del árbol DFS u -> v, la arista es un puente exactamente cuando low[v] > tin[u].

La tercera señal es la disciplina de implementación. En un vecino ya visitado, actualiza con tin[neighbor], no con low[neighbor]. Omite la arista exacta utilizada para ingresar a un nodo, no todas las aristas cuyo otro extremo sea igual al padre. Los ID de arista hacen explícita esa distinción y mantienen el código correcto si una pregunta de seguimiento permite aristas paralelas.

La cuarta señal es el conocimiento del lenguaje en entornos de producción. Un DFS recursivo es conciso, pero una cadena de 100 000 nodos puede exceder el límite de la pila de llamadas de un entorno de ejecución de JavaScript. Un DFS iterativo debe simular tanto la fase de entrada como la de retorno del hijo para propagar los valores de low solo después de que el hijo haya terminado.

Preguntas para clarificar antes de responder

• ¿Es un grafo dirigido? No. Los puentes en un grafo dirigido requieren una definición y un

algoritmo diferentes.

• ¿Se garantiza que el grafo sea conexo? Sí para el prompt base. Iterar sobre cada

nodo no visitado no añade costo asintótico y hace que la implementación funcione también para un seguimiento con grafos no conexos.

• ¿Se permiten aristas repetidas? No en el prompt base. Aun así, la implementación asigna un ID a cada

arista, de modo que dos aristas paralelas proporcionarían correctamente rutas alternativas en lugar de ser reportadas ambas como puentes.

• ¿El resultado puede usar cualquier orden de extremos? Sí. Si un evaluador automático requiere una salida canónica, normaliza

cada arista a [min, max] y ordena solo después de encontrar los puentes.

• ¿Es un grafo estático? Sí. Mantener los puentes mientras se insertan o eliminan aristas es un problema de

conectividad dinámica; volver a ejecutar este algoritmo lineal tras cada actualización puede resultar demasiado costoso.

• ¿Puedo usar recursión? Solo si el entorno garantiza suficiente profundidad de pila. Con n de hasta

100 000 en JavaScript o TypeScript, una pila explícita es el contrato más seguro.

Esquema de respuesta en 30 segundos

“Ejecutaría DFS una sola vez y asignaría a cada nodo un tiempo de descubrimiento tin. Para cada nodo, low registra el tiempo de descubrimiento más temprano alcanzable desde su subárbol DFS sin regresar por la arista de árbol exacta por la que se ingresó. Después de que un hijo v termina, si low[v] > tin[u], el subárbol bajo v no tiene ruta hacia u ni a un ancestro, por lo que [u, v] es un puente. De lo contrario, una arista de retroceso proporciona una ruta alternativa. Utilizaré IDs de arista y una pila explícita para DFS a fin de manejar preguntas de seguimiento con aristas paralelas y evitar desbordamientos de la pila de llamadas. Cada entrada de adyacencia se procesa una vez, por lo que el tiempo es O(n + m) y el espacio es O(n + m).”

Análisis paso a paso a profundidad

Comienza con la solución base correcta pero lenta. Para cada arista, ignórala temporalmente y realiza un recorrido desde uno de sus extremos. Si el otro extremo se vuelve inalcanzable, esa arista es un puente. Un solo recorrido toma O(n + m), por lo que todas las aristas toman O(m(n + m)). Este método puede ser razonable para un grafo minúsculo o una verificación aislada porque es fácil de auditar, pero no alcanza la escala requerida.

DFS expone todas las rutas alternativas en una sola pasada. Cuando se ingresa a un nodo u por primera vez, se asigna tin[u] = low[u] = timer y se incrementa timer. Un vecino recién visitado se convierte en un hijo en el DFS. Un vecino ya visitado al que se llega a través de una arista diferente es una conexión que no pertenece al árbol, por lo que puede reducir low[u] a tin[neighbor]. Una vez que un hijo v termina, todo su subárbol es conocido y low[u] = min(low[u], low[v]) propaga esa alcanzabilidad hacia arriba.

La comparación estricta es crucial. Si low[v] < tin[u], el subárbol del hijo alcanza a un ancestro de u. Si low[v] == tin[u], alcanza a u mismo a través de otra ruta. Ambos casos significan que la arista del árbol [u, v] se encuentra en un ciclo. Solo low[v] > tin[u] demuestra que cada ruta desde el subárbol del hijo hacia el lado ya descubierto utiliza [u, v].

Una implementación iterativa almacena nextIndex[u], la siguiente entrada de adyacencia que aún falta inspeccionar. El nodo permanece en la pila mientras sus hijos se ejecutan. Cuando se consumen todas sus entradas de adyacencia, se desapila; ese evento simula el retorno de la llamada recursiva y es el momento correcto para actualizar a su padre.

type AdjacentEdge = readonly [to: number, edgeId: number]

function findCriticalConnections(
  n: number,
  connections: ReadonlyArray<readonly [number, number]>,
): number[][] {
  const graph: AdjacentEdge[][] = Array.from({ length: n }, () => [])

  connections.forEach(([from, to], edgeId) => {
    graph[from].push([to, edgeId])
    graph[to].push([from, edgeId])
  })

  const tin = new Array<number>(n).fill(-1)
  const low = new Array<number>(n).fill(-1)
  const parent = new Array<number>(n).fill(-1)
  const parentEdge = new Array<number>(n).fill(-1)
  const nextIndex = new Array<number>(n).fill(0)
  const bridges: number[][] = []
  let timer = 0

  for (let root = 0; root < n; root += 1) {
    if (tin[root] !== -1) continue

    tin[root] = timer
    low[root] = timer
    timer += 1
    const stack = [root]

    while (stack.length > 0) {
      const node = stack[stack.length - 1]

      if (nextIndex[node] < graph[node].length) {
        const [neighbor, edgeId] = graph[node][nextIndex[node]]
        nextIndex[node] += 1

        if (edgeId === parentEdge[node]) continue

        if (tin[neighbor] === -1) {
          parent[neighbor] = node
          parentEdge[neighbor] = edgeId
          tin[neighbor] = timer
          low[neighbor] = timer
          timer += 1
          stack.push(neighbor)
        } else {
          low[node] = Math.min(low[node], tin[neighbor])
        }
      } else {
        stack.pop()
        const parentNode = parent[node]

        if (parentNode !== -1) {
          if (low[node] > tin[parentNode]) {
            bridges.push([parentNode, node])
          }
          low[parentNode] = Math.min(low[parentNode], low[node])
        }
      }
    }
  }

  return bridges
}

El bucle externo es redundante para la entrada conexa base, pero inicia correctamente un DFS en cada componente si esa garantía se elimina. Los IDs de arista son más robustos que omitir según el nodo padre. Con dos aristas paralelas entre u y v, el hijo omite solo la arista del árbol; la segunda arista se interpreta como una ruta alternativa y reduce su valor low.

Para la correctitud, considera una arista del árbol DFS u -> v después de que v ha terminado. Por la definición de low[v], un valor a lo sumo de tin[u] demuestra la existencia de una ruta que no pertenece al árbol desde el subárbol de v hacia u o un ancestro. Combinada con los caminos del árbol, esa ruta forma un ciclo que contiene a [u, v], por lo que eliminarla no puede separar el subárbol. Si low[v] > tin[u], no existe tal ruta. Todo camino desde ese subárbol hacia la parte previamente descubierta debe cruzar [u, v], por lo que eliminarla incrementa la cantidad de componentes. La condición es, por lo tanto, necesaria y suficiente.

Cada arista no dirigida aparece dos veces en las listas de adyacencia y cada entrada se inspecciona una vez. Cada nodo se inserta y se desapila una vez. El tiempo es O(n + m). El grafo, arreglos, pila y salida utilizan un espacio de O(n + m); excluyendo el grafo y la respuesta devuelta, el espacio auxiliar es de O(n).

Las pruebas adversarias deben comparar conjuntos de aristas normalizados, ya que el orden del resultado no está especificado. Una sola arista debe ser un puente; un ciclo no debe tener ninguno; cada arista de un árbol debe ser un puente; y dos ciclos unidos por una sola arista deben reportar únicamente el conector. Prueba también una cadena de 100 000 nodos para exponer riesgos en la pila de llamadas recursivas. Para mayor seguridad, genera pequeños grafos aleatorios y compara el algoritmo lineal con la solución base de eliminar una arista.

Respuesta de muestra de alta calidad

“Una solución directa elimina cada arista y vuelve a ejecutar un recorrido, pero eso cuesta O(m(n + m)). Puedo reutilizar un único DFS registrando el tiempo de descubrimiento y el tiempo de descubrimiento más temprano alcanzable desde cada subárbol del DFS.

Cuando entro al nodo u, inicializo tin[u] y low[u] con el temporizador actual. Un hijo en el árbol se procesa completamente antes de que su valor low se propague a u. Para un vecino ya visitado alcanzado por una arista diferente, actualizo con el tin de ese vecino, porque esa arista en sí representa el único escape que no pertenece al árbol cubierto por el invariante.

Después de que el hijo v termina, [u, v] es un puente exactamente cuando low[v] > tin[u]. La igualdad no es suficiente: significa que el subárbol tiene otra ruta de regreso hacia u, por lo que la arista pertenece a un ciclo. Un valor mayor significa que ningún nodo en el subárbol puede alcanzar a u o a un ancestro sin usar la arista del árbol, y eliminarla separa el subárbol.

Implementaría el DFS de forma iterativa debido al límite de 100 000 nodos. La pila conserva un nodo hasta que todas las entradas de adyacencia hayan sido procesadas, lo que me da un evento de retorno para propagar el valor low del hijo. También almaceno el ID de la arista padre y omito exactamente esa arista. Esto maneja correctamente un seguimiento con aristas paralelas. Cada entrada de adyacencia se inspecciona una vez, por lo que el tiempo es O(n + m) y el espacio total es O(n + m). Probaría un ciclo, un árbol, dos ciclos con un conector, una cadena larga, componentes desconectadas y aristas paralelas, y luego realizaría pruebas diferenciales con grafos aleatorios pequeños contra la solución base.”

Errores comunes

• Volver a ejecutar DFS para cada arista → la correctitud es válida pero el peor caso es cuadrático o peor →

Usa un solo DFS y preserva la información de rutas alternativas en low.

• Comprobar low[child] >= tin[parent] → la igualdad ya evidencia otro camino de regreso al

padre → Usa la condición estricta low[child] > tin[parent].

• Actualizar un vecino visitado con low[neighbor] → la alcanzabilidad desde otro subárbol DFS se filtra

a través de una arista que no es del árbol y puede ocultar un puente real → **Usa tin[neighbor] para un vecino ya visitado y low[child] solo después de que termine un hijo del árbol.**

• Omitir todas las aristas hacia el nodo padre → se ignoran todas las aristas paralelas y una de ellas podría reportarse

como puente → Asigna IDs de arista y omite únicamente la arista utilizada para ingresar al nodo.

• Evaluar si es puente antes de que el hijo termine → las rutas alternativas del hijo aún no se conocen →

Evalúa la condición durante la fase simulada de retorno.

• Iniciar únicamente en el nodo 0 → un caso de seguimiento no conexo perderá otras componentes → **Inicia desde cada

nodo que aún no haya sido visitado.**

• Usar recursión sin verificar los límites de la pila → una cadena larga puede fallar a pesar de la

complejidad lineal → Usa una pila explícita o demuestra que el entorno admite la profundidad requerida.

Preguntas de seguimiento y respuestas

Pregunta de seguimiento 1: ¿Qué cambia si el grafo es no conexo?

Define un puente como una arista cuya eliminación incrementa el número total de componentes conexas. La misma condición de low-link aplica dentro de cada componente. Inicia el DFS desde cada nodo cuyo tiempo de descubrimiento siga siendo -1; la implementación provista ya hace esto. No exijas que todo el grafo quede desconectado tras la eliminación.

Pregunta de seguimiento 2: ¿Qué sucede si se permiten aristas paralelas y bucles?

Mantén un ID único para cada arista y omite únicamente parentEdge[node]. Una segunda arista hacia el padre actúa entonces como una ruta fuera del árbol, evitando que cualquiera de las aristas paralelas se clasifique como puente. Un bucle actualiza un nodo con su propio tiempo de descubrimiento y nunca puede ser un puente. El prompt base excluye ambos casos, pero la identidad de las aristas en la implementación proporciona la extensión adecuada.

Pregunta de seguimiento 3: ¿Cómo devolverías puntos de articulación en su lugar?

Los datos de low-link son reutilizables, pero la condición se traslada de las aristas a los vértices. Un nodo no raíz u es un punto de articulación cuando tiene un hijo DFS v con low[v] >= tin[u]. Una raíz DFS es un punto de articulación solo cuando tiene al menos dos hijos en el árbol DFS. Observa que la igualdad pertenece a la condición de vértices, mientras que la detección de puentes utiliza el estricto >.

Pregunta de seguimiento 4: ¿Qué cambia cuando se agregan aristas continuamente?

Este algoritmo responde a una captura estática en tiempo lineal. Recalcular tras cada inserción cuesta O(n + m) por actualización. Una carga de trabajo de solo inserciones puede mantener la información de puentes con una estructura de datos online especializada; inserciones y eliminaciones arbitrarias requieren un diseño de conectividad dinámica más general. Clarifica el tipo de actualización, la frecuencia de consultas y el requisito de consistencia antes de seleccionar una.

Pregunta de seguimiento 5: ¿Cuándo sigue siendo mejor la solución base de búsqueda repetida?

Para un grafo diminuto, una sola arista sospechosa o código de diagnóstico donde la simplicidad prevalece sobre la latencia, omitir una arista y ejecutar BFS es más corto y fácil de inspeccionar. Menciona su costo de O(n + m) para una sola arista y evita introducir el estado de low-link a menos que la tarea realmente pida todos los puentes o consultas repetidas.