Para um dado DAG (gráfico acíclico direcionado), cada um de seus tipos topológicos é uma permutação de todos os vértices, onde para todas as arestas (u, v) no DAG, u aparece antes de v na permutação.

Sua tarefa é calcular o número total de tipos topológicos de um determinado DAG.

Regras

• Você pode usar qualquer formato para representar o gráfico, como matriz de adjacências, lista de adjacências ou lista de arestas, desde que não faça cálculos úteis em sua codificação. Você também pode ter itens como contagem de vértices ou lista de vértices na entrada, se forem úteis.
• Você pode assumir que o gráfico na entrada é sempre um DAG (não possui ciclos).
• Seu programa deve funcionar em teoria para qualquer entrada. Mas pode falhar se exceder o tipo inteiro básico no seu idioma.
• Os nomes dos vértices podem ser quaisquer valores consecutivos em qualquer tipo. Por exemplo: números começando em 0 ou 1. (E somente se você não estiver armazenando código nesse número, é claro).
• Isso é código-golfe. O menor código vence.

Exemplo

Esta é a mesma entrada em diferentes formatos. Seu programa não precisa aceitar todos eles. Os vértices são sempre números inteiros começando em 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] ]

É o gráfico mostrado nesta imagem:

A saída deve ser:

9

Os tipos topológicos são:

[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

Com grande ajuda do user23013 :)

Experimente online

Explicação:

O algoritmo geral é o mesmo da solução Python do xnor .
A chave aqui é o joperador, que faz recursão memorizada. É necessário um parâmetro, um valor ou matriz para os valores iniciais (como em f (0), f (1), etc) e um bloco para definir a recursão. O joperador é usado novamente dentro do bloco para fazer chamadas recursivas (e memorizadas) para o mesmo bloco. Também pode ser usado com vários parâmetros, mas não é o caso aqui.
A grande inovação do user23013 é usar j com diferentes tipos de dados, usando a lista de adjacências como matriz de valores iniciais.

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(…)"

Python, 58

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

A entrada consiste em um dicionário de adjacência Ge um 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}

O código é recursivo. O conjunto Varmazena todos os nós que ainda precisam ser visitados. Para cada próximo nó em potencial, verificamos sua adequação, verificando se nenhum vértice restante aponta para ele, V-G[v]==Vverificando isso Ve não G[v]é comum. Para todos esses vértices adequados, adicionamos o número de classificações topológicas com a remoção. Como base, o conjunto vazio fornece 1.

Mathematica, 80 57 51 bytes

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

Implementação muito direta da definição. Estou apenas gerando todas as permutações e conte quantas delas são válidas. Para verificar se uma permutação é válida, recebo todos os pares de vértices na permutação. Convenientemente, Subsets[l,{2}]não apenas me dá todos os pares, mas também mantém a ordem em que são encontrados l- exatamente o que eu preciso.

A descrição acima é uma função que espera a lista de vértices e a lista de arestas, como

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

se você chamar a função f.

Vou tentar jogar isso, ou talvez use outra abordagem mais tarde.

Pitão, 27 bytes

Mlf!sm}_dHfq2lYyTfqSZUZ^UGG

Define uma função de 2 entradas g,. A primeira entrada é o número de vértices, a segunda é a lista de arestas direcionadas.

Testar:

Code:
Mlf!sm}_dHfq2lYyTfqSZUZ^UGGghQeQ

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

Experimente aqui.

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

A entrada é o número de vértice mais alto (começando com 0) e uma lista de arestas, em que uma aresta é uma lista de dois elementos. Exemplo de uso:5 # [[0,1], [0,2], [0,3], [0,5], [1,2], [1,4], [3,2], [5,3]]

Como funciona: conte todas as permutações pdos vértices para os quais todas as arestas [u,v]atendem: a posição de uin pé menor que a posição de vin p. Essa é uma implementação direta da definição.

Edit: minha primeira versão retornou os tipos topológicos eles mesmos e não quantos existem. Corrigido.

Edição II: não funcionou para gráficos com vértices não conectados. Corrigido.