Dois vértices distintos em um gráfico direcionado estão fortemente conectados se houver um caminho no gráfico entre eles. Um componente fortemente conectado do gráfico é um subconjunto do gráfico, de modo que cada par de vértices distintos no subconjunto esteja fortemente conectado e a adição de mais vértices ao subconjunto quebraria essa propriedade.

Seu desafio é separar um gráfico em seus componentes fortemente conectados. Especificamente, você deve gerar todos os SCCs no gráfico.

E / S:

Como entrada, você pode usar uma lista de arestas direcionadas, uma lista de adjacências, uma matriz de adjacências ou qualquer outro formato de entrada razoável. Pergunte se você não tem certeza. Você pode assumir que o gráfico não possui vértices totalmente desconectados e que não existem arestas próprias, mas não pode fazer outras suposições. Você também pode opcionalmente levar a lista de vértices como entrada, bem como o número de vértices.

Como saída, você deve fornecer um particionamento dos vértices, como uma lista de listas de vértices, em que cada sub-lista é um componente fortemente conectado ou uma rotulagem de vértices, em que cada rótulo corresponde a um componente diferente.

Se você usar um rótulo, os rótulos deverão ser vértices ou uma sequência consecutiva de números inteiros. Isso evita que o cálculo seja desviado para os rótulos.

Exemplos:

Esses exemplos usam listas de arestas, em que cada aresta é direcionada da 1ª entrada para a segunda entrada e partições de saída. Você é livre para usar este formato ou outro.

A entrada está na primeira linha, a saída está na segunda linha.

[[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]]

Pontuação e restrições:

As brechas padrão são proibidas, como sempre. Além disso, os componentes internos que lidam especificamente com componentes fortemente conectados são banidos.

As soluções devem ser executadas em não mais de uma hora nos exemplos fornecidos. (Isso visa impedir soluções exponenciais lentas e nada mais.)

Isso é código de golfe. Menos bytes ganha.

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)

Recebe entrada como uma numpymatriz que representa a adjacência e o número de nós. Produz a saída como uma numpymatriz de linha que rotula cada vértice pelo número de vértice mais baixo em seu componente.

Para uma matriz de adjacência M, a potência da matriz M**nconta o número de ncaminhos -step de cada vértice inicial a cada vértice final. Adicionar a identidade Mvia M+M**0modifica a matriz de adjacência para adicionar um auto-loop a cada borda. Portanto, (M+M**0)**nconta caminhos de comprimento no máximo n(com redundância).

Como qualquer caminho tem no máximo comprimento n, o número de nós, qualquer (i,j)local em que o vértice jpossa ser alcançado icorresponde a uma entrada positiva de (M+M**0)**n. A matriz de acessibilidade é então R=(M+M**0)**n>0, onde a entrada >0funciona.

Computar a entrada andcomo R&R.T, onde R.Testá a transposição, fornece uma matriz indicando os pares de vértices mutuamente alcançáveis. É a ilinha é um vetor indicador para vértices no mesmo componente fortemente conectado. Tomando o seu argmaxde cada linha fornece o índice do primeiro Truenele, que é o índice do menor vértice em seu 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 uma lista de pares direcionados como argumento, enquanto o resultado é uma matriz para cada vértice, fornecendo o primeiro vértice fortemente conectado a ele, o que acredito ser considerado uma rotulagem válida. Por exemplo, com a 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]]ele retorna [, 1, 1, 3, 3, 1, 6, 6, 3](não há vértice 0; os vértices 1, 2 e 5 têm o rótulo 1; 3, 4 e 8 têm o rótulo 3, enquanto 6 e 7 têm o rótulo 6).

MATL , 26 22 bytes

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

Isso usa a mesma abordagem da resposta do @ xnor .

Funciona na versão atual (15.0.0) do idioma.

Input é a matriz de adjacência do gráfico, com linhas separadas por ponto e vírgula. Os primeiro e último casos de teste são

[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]

Experimente online!

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

Pitão, 13 bytes

.gu+Gs@LQG.{k

Demonstração , suíte de testes

Input é uma lista de adjacência, representada como um dicionário que mapeia vértices para a lista de vértices para os quais possui arestas (seus vizinhos direcionados). Saída é uma partição.

A essência do programa é que encontramos o conjunto de vértices que são alcançáveis ​​em cada vértice e, em seguida, agrupamos os vértices por esses conjuntos. Quaisquer dois vértices no mesmo SCC têm o mesmo conjunto de vértices acessíveis a partir deles, porque cada um é acessível pelo outro e a acessibilidade é transitiva. Quaisquer vértices em componentes diferentes têm conjuntos alcançáveis ​​diferentes, porque nenhum dos conjuntos contém o outro.

Explicação do 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