Dwa różne wierzchołki na ukierunkowanym wykresie są silnie połączone, jeśli na wykresie jest ścieżka od siebie do siebie. Silnie związany komponent wykresu jest podzbiorem wykresie tak, że każda para różnych wierzchołków w podgrupie są mocno połączone, oraz przez dodanie więcej wierzchołków podzbioru pęknie tę właściwość.

Wyzwanie polega na rozdzieleniu wykresu na jego silnie połączone komponenty. W szczególności musisz wyprowadzić wszystkie SCC na wykresie.

I / O:

Jako dane wejściowe możesz użyć listy skierowanych krawędzi, listy sąsiedztwa, macierzy sąsiedztwa lub innego rozsądnego formatu wejściowego. Zapytaj, jeśli nie jesteś pewien. Możesz założyć, że wykres nie ma całkowicie odłączonych wierzchołków i że nie ma żadnych krawędzi własnych, ale nie możesz przyjmować żadnych dalszych założeń. Opcjonalnie możesz również wziąć listę wierzchołków jako dane wejściowe, a także liczbę wierzchołków.

Jako wynik musisz podać partycję wierzchołków, na przykład listę list wierzchołków, gdzie każda podlista jest silnie połączonym składnikiem, lub etykietę wierzchołków, gdzie każda etykieta odpowiada innemu składnikowi.

Jeśli używasz etykietowania, etykiety muszą być wierzchołkami lub kolejną liczbą całkowitą. Ma to na celu uniknięcie rozplątywania obliczeń na etykietach.

Przykłady:

Te przykłady pobierają listy krawędzi, gdzie każda krawędź jest kierowana od pierwszego wpisu do drugiego wpisu, i partycje wyjściowe. Możesz używać tego formatu lub innego.

Dane wejściowe znajdują się w pierwszym wierszu, dane wyjściowe w drugim wierszu.

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

Punktacja i ograniczenia:

Standardowe luki są jak zawsze zakazane. Również wbudowane, które konkretnie dotyczą silnie połączonych komponentów są zabronione.

Rozwiązania powinny działać w nie więcej niż godzinę na podanych przykładach. (Ma to na celu zapobieganie powolnym wykładniczym rozwiązaniom i nic więcej.)

To jest kod golfowy. Wygrywa najmniej bajtów.

Python 2 używa numpy, 71 62 bajtów

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

Pobiera dane wejściowe jako numpymacierz reprezentującą przyleganie i liczbę węzłów. Generuje dane wyjściowe jako numpymacierz wierszy, która oznacza każdy wierzchołek najniższym numerem wierzchołka w jego składniku.

W przypadku macierzy przylegania Mmoc macierzy M**nzlicza liczbę nścieżek -step od każdego wierzchołka początkowego do każdego wierzchołka końcowego. Dodanie tożsamości do Mpoprzez M+M**0modyfikuje macierz przylegania, aby dodać pętlę własną do każdej krawędzi. Tak więc (M+M**0)**nliczy co najwyżej ścieżki długości n(z redundancją).

Ponieważ każda ścieżka ma co najwyżej długość n, liczba węzłów, gdziekolwiek można dotrzeć do (i,j)wierzchołka, odpowiada dodatniemu wpisowi . Macierz osiągalności jest więc tam, gdzie działa wejście.ji(M+M**0)**nR=(M+M**0)**n>0>0

Obliczenie wejścia andjako R&R.T, gdzie R.Tjest transpozycja, daje macierz wskazującą pary wzajemnie osiągalnych wierzchołków. Ten irząd jest wektorem wskaźnikowym dla wierzchołków w tym samym silnie połączonym składniku. Biorąc jego argmaxkażdego wiersza daje indeks pierwszego Truew nim, który jest indeksem najmniejszego wierzchołka w jego składniku.

JavaScript (ES6), 125 bajtów

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

Jako argument przyjmuje listę kierowanych par, a wynikiem jest tablica dla każdego wierzchołka, dając pierwszy wierzchołek silnie z nim związany, co moim zdaniem liczy się jako prawidłowe etykietowanie. Na przykład, z wejściem [[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]]zwraca [, 1, 1, 3, 3, 1, 6, 6, 3](nie ma wierzchołka 0; wierzchołki 1, 2 i 5 mają etykietę 1; 3, 4 i 8 mają etykietę 3, a 6 i 7 mają etykietę 6).

MATL , 26 22 bajtów

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

Wykorzystuje to to samo podejście, co odpowiedź @ xnor .

Działa w aktualnej wersji (15.0.0) języka.

Dane wejściowe to macierz przylegania wykresu z wierszami oddzielonymi średnikami. Pierwszy i ostatni przypadek testowy to

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

Wypróbuj 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 bajtów

.gu+Gs@LQG.{k

Demonstracja , pakiet testowy

Dane wejściowe to lista przylegania, reprezentowana jako słownik, który odwzorowuje wierzchołki na listę wierzchołków, do których ma krawędzie (skierowani sąsiedzi). Dane wyjściowe to partycja.

Istotą programu jest to, że znajdujemy zbiór wierzchołków, które są osiągalne z każdego wierzchołka, a następnie grupujemy wierzchołki według tych zbiorów. Dowolne dwa wierzchołki w tym samym SCC mają ten sam zestaw wierzchołków osiągalny z nich, ponieważ każdy jest osiągalny z drugiego, a osiągalność jest przechodnia. Dowolne wierzchołki w różnych komponentach mają różne zestawy osiągalne, ponieważ żaden z nich nie zawiera drugiego.

Objaśnienie kodu:

.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