Hay n cajas, numeradas del 1 al n . Cada casilla está bloqueada, de modo que solo se puede abrir con un tipo de clave correspondiente (también numerada de 1 a n ). Estas claves se distribuyen aleatoriamente en los cuadros (un cuadro puede tener cualquier número de claves, una clave puede tener cualquier número de duplicados), y luego todos los cuadros se cierran. También se ha encerrado un tesoro (numerado 0 ) en muchas de las cajas.

Has contratado a un cerrajero para recuperar todo el tesoro. Cobra por cada caja que abre. No hay ningún cargo por abrir una caja para la cual la llave ya está disponible.

La entrada es el contenido de cada cuadro. Puede decidir el formato de la entrada.

Produzca el costo mínimo requerido para obtener los tesoros.

Notas

1. Su algoritmo puede llevar mucho tiempo, pero eso es irrelevante.
2. El código más corto gana.
3. No es necesario preocuparse por la entrada no válida.

Data de muestra

Aquí la línea i representa las claves presentes en el cuadro i .

Entrada

2 0
3
4 0
5 6 0
6
0

Salida

1

Entrada

2 0
3 0

4 0
6
5 0

Salida

3

Entrada

2 4 0
3 0

1 0
6
5 0

Salida

2

Entrada

1
3 4


2 6
5

Salida

0

CJam, 59 52 50 49 45 43 42 bytes

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

¡Gracias a @ MartinBüttner por jugar 3 bytes y allanar el camino para 4 más!

Pruébelo en línea en el intérprete de CJam .

Cómo funciona

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&!}#=,

Esto es demasiado lento para el intérprete en línea.

Disección

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 es a quien quieres llamar.

No estoy seguro de si no debería usar un pseudo- Mapen [(Int,[Int])]su lugar (en lugar de [[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)