El objetivo de este desafío se le da un gráfico acíclico dirigido finito (DAG), determinar si el gráfico es una reducción transitiva .

Una breve explicación de lo que son un DAG y reducciones transitivas:

Un DAG es un gráfico con bordes dirigidos (es decir, solo puede viajar en una dirección en ese borde) de modo que dado cualquier nodo inicial en el gráfico, es imposible volver al nodo inicial (es decir, no hay ciclos).

Dado cualquier nodo inicial, si es posible viajar a otro nodo final en el gráfico a través de cualquier número positivo arbitrario de bordes, entonces ese nodo final se define como accesible desde el nodo inicial. En un DAG general, puede haber múltiples rutas que pueden tomarse desde un nodo inicial a un nodo final objetivo. Por ejemplo, tome este gráfico de diamantes:

Para llegar al nodo Dde A, usted podría tomar el camino A->B->Do A->C->D. Por lo tanto, Des accesible desde A. Sin embargo, no hay una ruta que se pueda tomar para llegar al nodo Bcomenzando desde el nodo C. Por lo tanto, el nodo Bno es accesible desde el nodo C.

Defina la accesibilidad del gráfico como la lista de nodos accesibles para cada nodo inicial en el gráfico. Entonces, para el mismo ejemplo de gráfico de diamante, la accesibilidad es:

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

A continuación se muestra otro gráfico que tiene la misma accesibilidad que el gráfico anterior:

Sin embargo, este segundo gráfico tiene más aristas que el gráfico original. La reducción transitiva de un gráfico es un gráfico con el menor número de aristas y la misma accesibilidad del gráfico original. Entonces, el primer gráfico es la reducción transitiva del segundo.

Para un DAG finito, se garantiza que la reducción transitiva existe y es única.

Entrada

La entrada es una "lista de listas", donde la lista externa tiene la longitud del número de vértices, y cada lista interna es la longitud del número de bordes que salen del nodo asociado y contiene los índices de los nodos de destino. Por ejemplo, una forma de describir el primer gráfico anterior sería (suponiendo una indexación basada en cero):

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

Puede comenzar a indexar el primer nodo en cualquier valor entero arbitrario (por ejemplo, indexación basada en 0 o 1).

La entrada puede provenir de cualquier fuente de entrada deseada (stdio, parámetro de función, etc.). Usted es libre de elegir el formato de entrada exacto siempre que no se proporcione información adicional. Por ejemplo, si desea tomar la entrada de stdio, puede hacer que cada línea sea una lista de bordes para el nodo asociado. Ex.:

1 2
3
3
'' (blank line)

Los índices en cada lista de adyacencia no están necesariamente ordenados, y podría haber múltiples bordes conectando dos nodos (ej .:) [[1,1],[]]. Puede suponer que el gráfico de entrada está débilmente conectado y no contiene ciclos (es decir, es un DAG).

Salida

La salida es verdadera si el DAG de entrada dado es una reducción transitiva, y un valor falso de lo contrario. Esto puede ser para cualquier sumidero deseado (stdio, valor de retorno, parámetro de salida, etc.)

Ejemplos

Todos los ejemplos usan indexación basada en 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

Puntuación

Este es el código de golf; el código más pequeño en bytes gana. Su código debe completarse en un período de tiempo razonable (10 minutos como máximo en cualquier hardware que tenga). Se aplican lagunas estándar. Puede usar los complementos deseados.

Ruby, 101 97 bytes

Enfoque simple que calcula el alcance de cada nodo y considera si se puede alcanzar un nodo hijo a través de cualquiera de los otros nodos. Aparentemente falla en los gráficos cíclicos, pero la definición de un DAG implica que no debería ser cíclico de todos modos.

Pruébalo en línea!

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

^{13 bytes guardados debido a @MartinEnder .}

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

Función anónima. Toma una lista anidada como entrada (basada en 1) y devuelve Trueo Falsecomo salida. La solución principal aquí es el byte 46 #~IsomorphicGraphQ~TransitiveReductionGraph@#&, que prueba si un gráfico dado es isomorfo a su reducción transitiva. El resto convierte la entrada en un Graphobjeto.

CJam (41 bytes)

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

Demostración en línea , arnés de prueba

Disección

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)

Jalea, 20 bytes

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

Utiliza indexación basada en 1. Pruébalo en línea!

Descripción general suelta

     €                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.