Dos vértices distintos en un gráfico dirigido están fuertemente conectados si hay un camino en el gráfico de cada uno al otro. Un componente fuertemente conectado del gráfico es un subconjunto del gráfico de tal manera que cada par de vértices distintos en el subconjunto están fuertemente conectados, y agregar más vértices al subconjunto rompería esta propiedad.

Su desafío es separar un gráfico en sus componentes fuertemente conectados. Específicamente, debe generar todos los SCC en el gráfico.

E / S:

Como entrada, puede usar una lista de aristas dirigidas, una lista de adyacencia, una matriz de adyacencia o cualquier otro formato de entrada razonable. Pregunta si no estás seguro. Puede suponer que el gráfico no tiene vértices totalmente desconectados y que no hay bordes propios, pero no puede hacer más suposiciones. Opcionalmente, también puede tomar la lista de vértices como entrada, así como la cantidad de vértices.

Como salida, debe dar una partición de los vértices, como una lista de listas de vértices, donde cada sublista es un componente fuertemente conectado, o una etiqueta de vértices, donde cada etiqueta corresponde a un componente diferente.

Si usa un etiquetado, las etiquetas deben ser vértices o una secuencia consecutiva de enteros. Esto es para evitar desplazar el cálculo en las etiquetas.

Ejemplos:

Estos ejemplos toman listas de aristas, donde cada arista se dirige desde la primera entrada a la segunda entrada, y las particiones de salida. Usted es libre de usar este formato u otro.

La entrada está en la primera línea, la salida está en la segunda línea.

[[1, 2], [2, 3], [3, 1], [1, 4]]
[[1, 2, 3], [4]]

[[1, 2], [2, 3], [3, 4]]
[[1], [2], [3], [4]]

[[1, 2], [2, 1], [1, 3], [2, 4], [4, 2], [4, 3]]
[[1, 2, 4], [3]]

[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]
[[1, 2, 5], [3, 4, 8], [6, 7]]

Puntuación y restricciones:

Las lagunas estándar están prohibidas, como siempre. Además, están prohibidos los elementos integrados que se ocupan específicamente de componentes fuertemente conectados.

Las soluciones deben ejecutarse en no más de una hora en los ejemplos proporcionados. (Esto está destinado a evitar soluciones exponenciales lentas, y nada más).

Este es el código de golf. Pocos bytes ganan.

Python 2 usando numpy, 71 62 bytes

import numpy
def g(M,n):R=(M+M**0)**n>0;print(R&R.T).argmax(0)

Toma la entrada como una numpymatriz que representa la adyacencia y el número de nodos. Produce salida como unnumpy matriz de filas que etiqueta cada vértice por el número de vértice más bajo en su componente.

Para una matriz de adyacencia M, la potencia de la matriz M**ncuenta el número de nrutas de paso desde cada vértice inicial hasta cada vértice final. Agregar la identidad a Mtravés de M+M**0modifica la matriz de adyacencia para agregar un bucle automático a cada borde. Entonces, (M+M**0)**ncuenta caminos de longitud como máximon (con redundancia).

Como cualquier ruta tiene una longitud como máximo n, el número de nodos, cualquiera desde (i,j)donde jse pueda alcanzar el vértice icorresponde a una entrada positiva de (M+M**0)**n. La matriz de accesibilidad es entonces R=(M+M**0)**n>0, donde el>0 funciona en sentido de entrada.

Al calcular la entrada andcomo R&R.T, donde R.Testá la transposición, se obtiene una matriz que indica los pares de vértices mutuamente accesibles. Su ifila es un vector indicador para vértices en el mismo componente fuertemente conectado. Al tomar el valor argmaxde cada fila, se obtiene el índice del primero True, que es el índice del vértice más pequeño de su componente.

JavaScript (ES6), 125 bytes

a=>a.map(([m,n])=>(e[m]|=1<<n|e[n],e.map((o,i)=>o&1<<m?e[i]|=e[m]:0)),e=[])&&e.map((m,i)=>e.findIndex((n,j)=>n&1<<i&&m&1<<j))

Toma una lista de pares dirigidos como argumento, mientras que el resultado es una matriz para cada vértice que le da al primer vértice fuertemente conectado a él, lo que creo que cuenta como un etiquetado válido. Por ejemplo, con la entrada [[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]devuelve [, 1, 1, 3, 3, 1, 6, 6, 3](no hay vértice 0; los vértices 1, 2 y 5 tienen etiqueta 1; 3, 4 y 8 tienen etiqueta 3 mientras que 6 y 7 tienen etiqueta 6).

MATL , 26 22 bytes

tnX^Xy+HMY^gt!*Xu!"@f!

Utiliza el mismo enfoque que la respuesta de @ xnor .

Funciona en la versión actual (15.0.0) del lenguaje.

La entrada es la matriz de adyacencia del gráfico, con filas separadas por punto y coma. Los primeros y últimos casos de prueba son

[0 1 0 1; 0 0 1 0; 1 0 0 0; 0 0 0 0]

[0 1 0 0 0 0 0 0; 0 0 1 0 1 1 0 0; 0 0 0 1 0 0 1 0; 0 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 1 0 0; 0 0 0 1 0 0 1 0]

Pruébalo en línea!

t     % implicitly input adjacency matrix. Duplicate
n     % number of elements
X^    % square root
Xy    % identity matrix of that size
+     % add to adjacency matrix
HM    % push size again
Y^    % matrix power
g     % convert to logical values (0 and 1)
t!*   % multiply element-wise by transpose matrix
Xu    % unique rows. Each row is a connected component
!     % transpose
"     % for each column
  @   %   push that column
  f!  %   indices of nonzero elements, as a row
      % end for each. Implicitly display stack contents

Pyth, 13 bytes

.gu+Gs@LQG.{k

Demostración , conjunto de pruebas

La entrada es una lista de adyacencia, representada como un diccionario que asigna vértices a la lista de vértices a los que tiene bordes (sus vecinos dirigidos). La salida es una partición.

La esencia del programa es que encontramos el conjunto de vértices a los que se puede llegar desde cada vértice, y luego agrupamos los vértices por esos conjuntos. Cualquiera de los dos vértices en el mismo SCC tiene el mismo conjunto de vértices accesibles desde ellos, porque cada uno es accesible desde el otro y la accesibilidad es transitiva. Cualquier vértice en diferentes componentes tiene diferentes conjuntos accesibles, porque ninguno de los dos contiene el otro.

Explicación del código:

.gu+Gs@LQG.{k
                  Implicit: Q is the input adjacency list.
.g           Q    Group the vertices of Q by (Q is implicit at EOF)
  u       .{k     The fixed point of the following function, 
                  starting at the set containing just that vertex
   +G             Add to the set
     s            The concatenation of
      @LQG        Map each prior vertex to its directed neighbors