Zwei verschiedene Eckpunkte in einem gerichteten Graphen sind stark verbunden, wenn der Graphen einen Pfad von einem zum anderen aufweist. Eine stark verbundene Komponente des Diagramms ist eine Teilmenge des Diagramms, sodass jedes Paar unterschiedlicher Scheitelpunkte in der Teilmenge stark verbunden ist, und das Hinzufügen weiterer Scheitelpunkte zur Teilmenge würde diese Eigenschaft aufheben.

Ihre Herausforderung besteht darin, ein Diagramm in seine eng miteinander verbundenen Komponenten zu unterteilen. Insbesondere müssen Sie alle SCCs im Diagramm ausgeben.

I / O:

Als Eingabe können Sie eine Liste gerichteter Kanten, eine Adjazenzliste, eine Adjazenzmatrix oder ein anderes angemessenes Eingabeformat verwenden. Fragen Sie, ob Sie sich nicht sicher sind. Sie können davon ausgehen, dass das Diagramm keine vollständig getrennten Scheitelpunkte hat und dass es keine Selbstkanten gibt, aber Sie können möglicherweise keine weiteren Annahmen treffen. Optional können Sie auch die Liste der Scheitelpunkte als Eingabe sowie die Anzahl der Scheitelpunkte verwenden.

Als Ausgabe müssen Sie entweder eine Partitionierung der Scheitelpunkte angeben, z. B. eine Liste von Scheitelpunktlisten, bei der jede Unterliste eine stark verbundene Komponente ist, oder eine Beschriftung von Scheitelpunkten, bei der jede Beschriftung einer anderen Komponente entspricht.

Wenn Sie eine Beschriftung verwenden, müssen die Beschriftungen entweder Eckpunkte oder eine aufeinanderfolgende Folge von ganzen Zahlen sein. Dies soll verhindern, dass die Berechnung in die Etiketten verschoben wird.

Beispiele:

In diesen Beispielen werden Kantenlisten erstellt, in denen jede Kante vom ersten zum zweiten Eintrag geleitet wird, und Partitionen ausgegeben. Sie können dieses oder ein anderes Format verwenden.

Der Eingang befindet sich in der ersten Zeile, der Ausgang in der zweiten Zeile.

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

Wertung und Einschränkungen:

Standardlücken sind wie immer verboten. Außerdem sind eingebaute Komponenten, die sich speziell mit stark verbundenen Komponenten befassen, verboten.

Die Lösungen sollten nach den angegebenen Beispielen nicht länger als eine Stunde dauern. (Dies soll langsame exponentielle Lösungen und nichts anderes verhindern.)

Das ist Code Golf. Wenigste Bytes gewinnt.

Python 2 mit Numpy, 71 62 Bytes

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

Nimmt die Eingabe als numpyMatrix, die die Nachbarschaft und die Anzahl der Knoten darstellt. Erzeugt die Ausgabe als numpyZeilenmatrix, die jeden Scheitelpunkt mit der niedrigsten Scheitelpunktnummer in seiner Komponente beschriftet.

Für eine Adjazenzmatrix M, die Matrix - Leistungs M**nzählt die Anzahl der n-Schritt Pfade von jedem Anfangsknoten zu jedem Endknoten. Durch Hinzufügen der Identität zu Mvia wird M+M**0die Adjazenzmatrix so geändert, dass jeder Kante eine Selbstschleife hinzugefügt wird. So (M+M**0)**nzählt Wege der Länge höchstens n(mit Redundanz).

Da jeder Pfad höchstens eine Länge hat n, entspricht die Anzahl der Knoten, von (i,j)denen aus jeder Scheitelpunkt erreicht werden jkann i, einem positiven Eintrag von (M+M**0)**n. Die Erreichbarkeitsmatrix ist dann R=(M+M**0)**n>0, wo das >0eingangsseitig funktioniert.

Berechnet man den eingangsweisen Wert andals R&R.T, wo R.Tsich die Transponierte befindet, so erhält man eine Matrix, die die Paare der miteinander erreichbaren Eckpunkte angibt. Die idritte Zeile ist ein Indikatorvektor für Scheitelpunkte in derselben stark verbundenen Komponente wie sie. Aus argmaxjeder Zeile wird der Index der ersten Truein der Zeile genommen , der der Index des kleinsten Scheitelpunkts in seiner Komponente ist.

JavaScript (ES6), 125 Byte

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))

Nimmt eine Liste gerichteter Paare als Argument, während das Ergebnis ein Array für jeden Scheitelpunkt ist, das den ersten Scheitelpunkt angibt, der eng damit verbunden ist, was meiner Meinung nach als gültige Bezeichnung gilt. Beispiel: Bei der Eingabe [[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]], die zurückgegeben wird [, 1, 1, 3, 3, 1, 6, 6, 3](es gibt keinen Scheitelpunkt 0; Scheitelpunkte 1, 2 und 5 haben die Bezeichnung 1; 3, 4 und 8 haben die Bezeichnung 3, während 6 und 7 die Bezeichnung 6 haben).

MATL , 26 22 Bytes

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

Dies verwendet den gleichen Ansatz wie die Antwort von @ xnor .

Funktioniert in der aktuellen Version (15.0.0) der Sprache.

Die Eingabe ist die Adjazenzmatrix des Diagramms mit durch Semikolons getrennten Zeilen. Der erste und der letzte Testfall sind

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

Probieren Sie es 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

Pyth, 13 Bytes

.gu+Gs@LQG.{k

Vorführung , Testsuite

Die Eingabe ist eine Adjazenzliste, die als Wörterbuch dargestellt wird und Scheitelpunkte der Liste von Scheitelpunkten zuordnet, zu denen sie Kanten hat (ihre gerichteten Nachbarn). Ausgabe ist eine Partition.

Die Essenz des Programms besteht darin, dass wir die Menge der Scheitelpunkte finden, die von jedem Scheitelpunkt aus erreichbar sind, und dann die Scheitelpunkte nach diesen Mengen gruppieren. Zwei beliebige Scheitelpunkte in derselben SCC haben denselben Satz von Scheitelpunkten, die von ihnen aus erreichbar sind, da jeder von dem anderen aus erreichbar ist und die Erreichbarkeit transitiv ist. Alle Scheitelpunkte in verschiedenen Komponenten haben unterschiedliche erreichbare Mengen, da keine der beiden Mengen die andere enthält.

Code Erklärung:

.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