Es gibt n Kästchen mit der Nummer 1-n . Jede Box ist gesperrt, sodass sie nur mit einem entsprechenden Schlüsseltyp (auch mit 1-n nummeriert ) geöffnet werden kann . Diese Schlüssel werden zufällig in den Feldern verteilt (ein Feld kann eine beliebige Anzahl von Schlüsseln enthalten, ein Schlüssel kann eine beliebige Anzahl von Duplikaten enthalten), und dann werden alle Felder geschlossen. Ein Schatz (mit der Nummer 0 ) wurde ebenfalls in vielen Kisten eingeschlossen.

Sie haben einen Schlosser engagiert, um den ganzen Schatz zu bergen. Er berechnet für jede Kiste, die er aufbricht. Das Öffnen einer Box, für die der Schlüssel bereits verfügbar ist, ist kostenlos.

Die Eingabe ist der Inhalt jeder Box. Sie können das Format der Eingabe festlegen.

Geben Sie die minimalen Kosten aus, die erforderlich sind, um die Schätze zu erhalten.

Anmerkungen

1. Ihr Algorithmus kann lange dauern, aber das ist irrelevant.
2. Kürzester Code gewinnt.
3. Keine Notwendigkeit, sich um ungültige Eingaben zu kümmern.

Beispieldaten

Hier repräsentiert die Linie i die in Kasten i vorhandenen Schlüssel .

Eingang

2 0
3
4 0
5 6 0
6
0

Ausgabe

1

Eingang

2 0
3 0

4 0
6
5 0

Ausgabe

3

Eingang

2 4 0
3 0

1 0
6
5 0

Ausgabe

2

Eingang

1
3 4


2 6
5

Ausgabe

0

CJam, 59 52 50 49 45 43 42 Bytes

qN/ee::~e!{_0+{0a&}#>W%_{1$|(z@-},,\;}%:e<

Vielen Dank an @ MartinBüttner für das Abschlagen von 3 Bytes und den Weg für weitere 4 Bytes!

Probieren Sie es online im CJam-Interpreter aus .

Wie es funktioniert

qN/      e# Read all input and split it at linefeeds.
ee       e# Enumerate the lines.
         e# STACK: [[0 "i0 i1 ..."] [1 "j0 j1 ..."] ...]
::~      e# Apply ~ (bitwise NOT/evaluate) to each item of the pairs.
         e# STACK: [[-1 i0 i1 ...] [-2 j0 j1 ...] ...]
e!       e# Push all unique permutations of the resulting array.
{        e# For each permutation:
  _0+    e#   Push a copy and append 0 to it.
  {0a&}# e#   Find the first index of an element that contains 0.
  >      e#   Discard all previous elements of the array.
  W%     e#   Reverse the resulting array.
         e#   We now have a (partial) permutation that contains
         e#   all treasures and ends with a treasure.
  _      e#   Push a copy. The original (which contains lists, but no 
              numbers) will serve as accumulator.
  {      e#   Filter; for each list in the array:
    1$|  e#     Push a copy of the accumulator and perform set union.
    (    e#     Shift out the first element (bitwise NOT of 0-based index).
    z    e#     Apply absolute value to push the 1-based index.
    @-   e#     Perform set difference with the former state of the 
         e#     accumulator. This pushes an empty list iff the 1-based
         e#     index was already in the accumulator, i.e., iff we already
         e#     had a key.
  },     e#   Keep the element if we did not have the key.
  ,      e#   Count the kept elements.
  \;     e#   Discard the accumulator from the stack.
}%       e#
:e<      e# Get the minimum of all results.

CJam (53 Bytes)

Nq+N/:a::~:A,_m*_.&{,}$_{{_Af=e_|}:PA,*A,,^0-P0&!}#=,

Dies ist für den Online-Dolmetscher eher zu langsam.

Präparation

Nq+N/:a::~:A      e# Parse the input into arrays and store in A
,_m*_.&           e# Generate (with duplicates) a powerset of [0 1 ... n]
{,}$              e# Sort by size
_{                e# Create a copy and search for first index satisfying...
  {_Af=e_|}:P     e#   Store in P a block which does a reachability expansion
  A,*             e#   Apply it n times (no path can be longer than n)
  A,,^0-          e#   Invert to get the unreached nodes (except 0)
  P               e#   Apply P again to see what's reached from the unreached nodes
  0&!             e#   Check that it doesn't include [0]
}#
=,                e# Look up the powerset element at that index and find length

Haskell, 173 Bytes

l ist derjenige, den du anrufen willst.

Nicht sicher , ob ich nicht einen pseudo- verwenden sollte Mapstatt ( [(Int,[Int])]statt [[Int]]).

l=o[].map(map read).map words.lines
o[]b|0`notElem`concat b=0|0<1=1+minimum[o[n]b|n<-[1..length b],b!!(n-1)/=[]]
o(n:k)b=o(filter(/=0)(k++b!!(n-1)))(take(n-1)b++[]:drop n b)