Celem tego wyzwania jest skończony ukierunkowany wykres acykliczny (DAG), określenie, czy wykres jest redukcją przechodnią .

Krótkie wyjaśnienie, czym są DAG i redukcje przechodnie:

DAG jest wykresem z ukierunkowanymi krawędziami (tzn. Na tej krawędzi można podróżować tylko w jednym kierunku), tak że biorąc pod uwagę dowolny węzeł początkowy na wykresie, nie można powrócić do węzła początkowego (tzn. Nie ma cykli).

Biorąc pod uwagę dowolny węzeł początkowy, jeśli możliwe jest przejście do innego węzła końcowego na wykresie za pomocą dowolnej dodatniej liczby krawędzi, wówczas ten węzeł końcowy jest definiowany jako osiągalny z węzła początkowego. W ogólnym DAG może istnieć wiele ścieżek, które można wziąć z węzła początkowego do docelowego węzła końcowego. Na przykład weź ten wykres diamentów:

Aby dostać się do węzła Dz A, można podjąć ścieżkę A->B->Dlub A->C->D. W ten sposób Djest osiągalny z A. Jednak nie ma ścieżki, którą można by dostać się do węzła Bzaczynając od węzła C. Zatem węzeł Bnie jest osiągalny z węzła C.

Zdefiniuj osiągalność wykresu jako listę osiągalnych węzłów dla każdego początkowego węzła na wykresie. Tak więc dla tego samego przykładowego wykresu diamentów osiągalność jest następująca:

A: [B, C, D]
B: [D]
C: [D]
D: []

Inny wykres, który ma taką samą osiągalność jak powyższy wykres, pokazano poniżej:

Jednak ten drugi wykres ma więcej krawędzi niż oryginalny wykres. Przejściowa redukcja wykresu to wykres z najmniejszą liczbą krawędzi i taką samą osiągalnością jak oryginalny wykres. Tak więc pierwszy wykres jest przechodnią redukcją drugiego.

W przypadku skończonego DAG gwarantowane jest, że redukcja przechodnich istnieje i jest unikalna.

Wejście

Dane wejściowe to „lista list”, gdzie lista zewnętrzna ma długość liczby wierzchołków, a każda lista wewnętrzna jest długością liczby krawędzi wychodzących z powiązanego węzła i zawiera wskaźniki węzłów docelowych. Na przykład jednym ze sposobów opisania pierwszego powyższego wykresu byłoby (przy założeniu indeksowania zerowego):

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

Możesz rozpocząć indeksowanie pierwszego węzła przy dowolnej dowolnej wartości całkowitej (np. Indeksowanie na podstawie 0 lub 1).

Sygnał wejściowy może pochodzić z dowolnego żądanego źródła wejściowego (standard, parametr funkcji itp.). Możesz wybrać dokładny format wejściowy, o ile nie zostaną podane dodatkowe informacje. Na przykład, jeśli chcesz pobierać dane wejściowe ze standardowego interfejsu, każda linia może być listą krawędzi dla powiązanego węzła. Dawny.:

1 2
3
3
'' (blank line)

Indeksy na każdej liście sąsiadów niekoniecznie są posortowane i może istnieć wiele krawędzi łączących dwa węzły (np .:) [[1,1],[]]. Możesz założyć, że wykres wejściowy jest słabo połączony i nie zawiera cykli (tzn. Jest to DAG).

Wynik

Dane wyjściowe są zgodne z prawdą, jeśli dane wejściowe DAG są redukcją przechodnią, a wartością fałszowania w przeciwnym razie. Może to być dowolny pożądany zlew (stdio, wartość zwracana, parametr wyjściowy itp.)

Przykłady

Wszystkie przykłady używają indeksowania opartego na 0.

[[1,2],[3],[3],[]]
true

[[1,2,3],[3],[3],[]]
false

[[1,1],[]]
false

[[1,2,3,4],[5,6,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true

[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
true

[[5,6,7],[2,3,0,4,14,5,7],[5,8,9],[6,8,10],[7,9,10],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false

[[5,6,7],[2,3,0,4],[5,8,9],[6,8,10],[7,9,10,14],[11,12],[11,13],[12,13],[11,14],[12,14],[13,14],[],[],[],[]]
false

[[1,3],[2],[3],[]]
false

Punktacja

To jest kod golfowy; najmniejszy kod w bajtach wygrywa. Twój kod powinien zostać wypełniony w rozsądnym czasie (maksymalnie 10 minut na dowolnym sprzęcie). Obowiązują standardowe luki. Możesz użyć dowolnych wbudowanych funkcji.

Ruby, 101 97 bajtów

Proste podejście, które oblicza zasięg z każdego węzła i rozważa, czy do węzła potomnego można dotrzeć za pośrednictwem dowolnego z innych węzłów. Niby zawodzi na cyklicznych grafach, ale definicja DAG sugeruje, że i tak nie powinna być cykliczna.

Wypróbuj online!

->g{r=->i{i|i.map{|j|r[g[j]||[]]}.inject([],:|)}
g.all?{|e|e==e&e&&e.none?{|i|r[e-[i]].index i}}}

Mathematica, 95 82 bajtów

^{13 bajtów zapisanych z powodu @MartinEnder .}

#~IsomorphicGraphQ~TransitiveReductionGraph@#&@Graph[x=0;##&@@Thread[++x->#]&/@#]&

Funkcja anonimowa. Pobiera zagnieżdżoną listę jako dane wejściowe (oparte na 1) i zwraca Truelub Falsejako dane wyjściowe. Głównym rozwiązaniem jest tutaj 46-bajtowy #~IsomorphicGraphQ~TransitiveReductionGraph@#&, który sprawdza, czy dany wykres jest izomorficzny w stosunku do redukcji przechodniej. Reszta przekształca dane wejściowe w Graphobiekt.

CJam (41 bajtów)

q~:A_,{{Af=e__&}%_}*]:.|A.&A:$:e`e_2%1-*!

Demo online , uprząż testowa

Sekcja

q~:A      e# Parse input and store in A
_,{       e# Loop V times
  {       e#   Extend adjacency list representation of G^i to G^(i+1)
    Af=   e#   by extending each path by one edge
    e__&  e#   and flattening. NB :| would be shorter but breaks for empty lists
  }%
  _       e#   Duplicate, so that we build up G^2, G^3, ..., G^n
}*]       e# Gather in a single array
:.|       e# Fold pointwise union, giving the reachability from each vertex by
          e# paths of length > 1
A.&       e# Pointwise intersect with the paths of length 1
          e# We hope to get an array of empty arrays

          e# Handle the awkward special case of duplicate edges:
A:$       e# Sort each adjacency list
:e`       e# Run-length encode each adjacency list
e_2%      e# Extract only the run lengths
1-        e# Discard the 1s - so we now have an empty array unless there's a dupe

*         e# Join. We hope to be joining an array of empty arrays by an empty array
          e# giving an empty array
!         e# Check that we get a falsy value (i.e. the empty array)

Galaretka, 20 bajtów

ị³$ÐĿ€ị@Fœ&¥";œ-Q$€E

Wykorzystuje indeksowanie 1. Wypróbuj online!

Luźny przegląd

     €                for each vertex,
ị³$ÐĿ                   compute its reach.
        Fœ&¥"         intersect each vertex's lists of children and
      ị@                children's reaches.
             ;        then concatenate the list of intersections with
              œ-Q$€     all duplicate edges in the original graph.
                   E  are all elements equal? checks that all are empty lists,
                        meaning empty intersections and no duplicates.