Para un DAG dado (gráfico acíclico dirigido), cada uno de sus tipos topológicos es una permutación de todos los vértices, donde para cada borde (u, v) en el DAG, u aparece antes de v en la permutación.

Su tarea es calcular el número total de tipos topológicos de un DAG dado.

Reglas

• Puede usar cualquier formato para representar el gráfico, como la matriz de adyacencia, la lista de adyacencia o la lista de bordes, siempre que no realice cálculos útiles en su codificación. También puede tener cosas como conteo de vértices o lista de vértices en la entrada, si son útiles.
• Puede suponer que el gráfico en la entrada siempre es un DAG (no tiene ningún ciclo).
• Su programa debería funcionar en teoría para cualquier entrada. Pero puede fallar si desborda el tipo entero básico en su idioma.
• Los nombres de vértices pueden ser cualquier valor consecutivo en cualquier tipo. Por ejemplo: números que comienzan en 0 o 1. (Y solo si no está almacenando código en este número, por supuesto).
• Este es el código de golf. El código más corto gana.

Ejemplo

Esta es la misma entrada en diferentes formatos. Su programa no tiene que aceptarlos todos. Los vértices son siempre enteros comenzando en 0.

Adjacency list:
[ [1 2 3 5] [2 4] [] [2] [] [3] ]
Adjacency matrix:
[ [0 1 1 1 0 1] [0 0 1 0 1 0] [0 0 0 0 0 0] [0 0 1 0 0 0] [0 0 0 0 0 0] [0 0 0 1 0 0] ]
Edge list:
6 [ [0 1] [0 2] [0 3] [0 5] [1 2] [1 4] [3 2] [5 3] ]

Es el gráfico que se muestra en esta imagen:

La salida debe ser:

9

Los tipos topológicos son:

[0 1 4 5 3 2]
[0 1 5 4 3 2]
[0 1 5 3 4 2]
[0 1 5 3 2 4]
[0 5 1 4 3 2]
[0 5 1 3 4 2]
[0 5 1 3 2 4]
[0 5 3 1 4 2]
[0 5 3 1 2 4]

CJam - 25

q~{_f{1$-_j@j@&!*}_!+:+}j

Con gran ayuda de user23013 :)

Pruébalo en línea

Explicación:

El algoritmo general es el mismo que en la solución Python de xnor .
La clave aquí es el joperador, que hace una recursión memorable. Se necesita un parámetro, un valor o matriz para los valores iniciales (como en f (0), f (1), etc.) y un bloque para definir la recursividad. El joperador se usa nuevamente dentro del bloque para hacer llamadas recursivas (y memorizadas) al mismo bloque. También se puede usar con múltiples parámetros, pero no es el caso aquí.
La gran innovación de user23013 es usar j con diferentes tipos de datos, haciendo uso de la lista de adyacencia como la matriz de valores iniciales.

q~             read and evaluate the input (vertex list followed by adjacency list)
{…}j           run the block on the vertex list, doing memoized recursion
                and using the adjacency list for initial values
    _          copy the vertex list
    f{…}       for each vertex and the vertex list
        1$-    copy the vertex and remove it from the list
                Python: "V-{v}"
        _j     copy the reduced list and call the j block recursively
                this solves the problem for the reduced vertex list
                Python: "f(G,V-{v})"
        @j     bring the vertex to the top of the stack and call the j block recursively
                in this case, it's called with a vertex rather than a list
                and the memoized value is instantly found in the list of initial values
                effectively, this gets the list of vertices adjacent to the current vertex
                Python: "G[v]"
        @&     bring the reduced list to the top of the stack and intersect
        !*     multiply the number of topological sorts of the reduced vertex list
                with 1 if the intersection was empty and 0 if not
                Python: equivalent to "*(V-G[v]==V)"
               after this loop we get an array of sub-results for the reduced vertex lists
    _!+        add 1 or 0 to the array if the array was empty or not
                because we want to get 1 for the empty array
                Python: equivalent to "V<{0}or"
    :+         add the numbers in the array
                Python: "sum(…)"

Pitón, 58

f=lambda G,V:V<{0}or sum(f(G,V-{v})*(V-G[v]==V)for v in V)

La entrada consiste en un diccionario de adyacencia Gy un conjunto de vértices V.

G = {0:{1,2,3,5}, 1:{2,4}, 2:set(), 3:{2}, 4:set(), 5:{3}, 6:set()}
V = {0,1,2,3,4,5}

El código es recursivo. El conjunto Valmacena todos los nodos que aún necesitan visita. Para cada próximo nodo potencial, verificamos su idoneidad al ver si no hay vértices restantes que lo señalen, y V-G[v]==Vverificamos eso Vy G[v]somos disjuntos. Para todos los vértices adecuados, agregamos el número de tipos topológicos eliminados. Como caso base, el conjunto vacío da 1.

Mathematica, 80 57 51 bytes

Count[Permutations@#,l_/;l~Subsets~{2}~SubsetQ~#2]&

Implementación muy directa de la definición. Solo estoy generando todas las permutaciones y cuento cuántas de ellas son válidas. Para verificar si una permutación es válida, obtengo todos los pares de vértices en la permutación. Convenientemente, Subsets[l,{2}]no solo me da todos los pares, sino que también mantiene el orden en el que se encuentran l, justo lo que necesito.

Lo anterior es una función que espera la lista de vértices y la lista de bordes, como

f[{1, 2, 3, 4, 5, 6}, {{1, 2}, {1, 3}, {1, 4}, {1, 6}, {2, 3}, {2, 5}, {4, 3}, {6, 4}}]

si se llama a la función f.

Intentaré jugar al golf, o tal vez use otro enfoque más tarde.

Pyth, 27 bytes

Mlf!sm}_dHfq2lYyTfqSZUZ^UGG

Define una función 2 de entrada, g. La primera entrada es el número de vértices, la segunda es la lista de aristas dirigidas.

Probar:

Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

Input:
6, [ [0, 1], [0, 2], [0, 3], [0, 5], [1, 2], [1, 4], [3, 2], [5, 3] ]

Pruébalo aquí.

Haskell, 102 107 100 89 85 bytes

import Data.List
(%)=elemIndex
n#l=sum[1|p<-permutations[0..n],and[u%p<v%p|[u,v]<-l]]

La entrada es el número de vértice más alto (comenzando con 0) y una lista de bordes, donde un borde es una lista de dos elementos. Ejemplo de uso:5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]

Cómo funciona: cuente todas las permutaciones pde los vértices para los que [u,v]satisfacen todos los bordes : la posición de uin pes menor que la posición de vin p. Esa es una implementación directa de la definición.

Editar: mi primera versión devolvió los tipos topológicos y no cuántos hay. Arreglado.

Edición II: no funcionó para gráficos con vértices no conectados. Arreglado.