O objetivo deste desafio é fornecer um gráfico acíclico direcionado finito (DAG), determinar se o gráfico é uma redução transitiva .

Uma breve explicação do que são DAG e reduções transitivas:

Um DAG é um gráfico com arestas direcionadas (ou seja, você só pode viajar em uma direção nessa aresta), de modo que, dado qualquer nó inicial no gráfico, é impossível retornar ao nó inicial (ou seja, não há ciclos).

Dado qualquer nó inicial, se for possível viajar para outro nó final no gráfico por meio de qualquer número positivo arbitrário de arestas, esse nó final é definido como acessível a partir do nó inicial. Em um DAG geral, pode haver vários caminhos que podem ser tomados de um nó inicial para um nó final de destino. Por exemplo, veja este gráfico de diamante:

Para chegar ao nó Dde A, você pode pegar o caminho A->B->Dou A->C->D. Assim, Dé acessível a partir de A. No entanto, não há um caminho que possa ser seguido para chegar ao nó Biniciando no nó C. Assim, o nó Bnão está acessível a partir do nó C.

Defina a acessibilidade do gráfico como a lista de nós alcançáveis ​​para cada nó inicial no gráfico. Portanto, para o mesmo exemplo de gráfico de diamante, a acessibilidade é:

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

Outro gráfico que tem a mesma acessibilidade que o gráfico acima é mostrado abaixo:

No entanto, este segundo gráfico possui mais arestas que o gráfico original. A redução transitiva de um gráfico é um gráfico com o menor número de arestas e a mesma acessibilidade do gráfico original. Portanto, o primeiro gráfico é a redução transitiva do segundo.

Para um DAG finito, a redução transitiva é garantida e é única.

Entrada

A entrada é uma "lista de listas", em que a lista externa possui o comprimento do número de vértices e cada lista interna é o comprimento do número de arestas que saem do nó associado e contém os índices dos nós de destino. Por exemplo, uma maneira de descrever o primeiro gráfico acima seria (assumindo a indexação baseada em zero):

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

Você pode começar a indexação do primeiro nó em qualquer valor inteiro arbitrário (por exemplo, indexação baseada em 0 ou 1).

A entrada pode vir de qualquer fonte de entrada desejada (stdio, parâmetro de função, etc.). Você pode escolher o formato exato de entrada, desde que nenhuma informação adicional seja fornecida. Por exemplo, se você deseja receber a entrada do stdio, cada linha pode ser uma lista de arestas para o nó associado. Ex.:

1 2
3
3
'' (blank line)

Os índices em cada lista de adjacência não são necessariamente classificados e pode haver várias arestas conectando dois nós (ex .:) [[1,1],[]]. Você pode assumir que o gráfico de entrada está fracamente conectado e não contém ciclos (ou seja, é um DAG).

Resultado

A saída é verdadeira se a entrada DAG fornecida for uma redução transitiva e, caso contrário, um valor falso. Pode ser em qualquer coletor desejado (stdio, valor de retorno, parâmetro de saída, etc.)

Exemplos

Todos os exemplos usam indexação baseada em 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

Pontuação

Isso é código de golfe; o menor código em bytes vence. Seu código deve ser concluído em um período de tempo razoável (10 minutos no máximo em qualquer hardware que você tenha). Aplicam-se brechas padrão. Você pode usar quaisquer embutidos desejados.

Ruby, 101 97 bytes

Abordagem simples que calcula o alcance de cada nó e considera se um nó filho pode ser alcançado através de qualquer um dos outros nós. Aparentemente falha em gráficos cíclicos, mas a definição de um DAG implica que não deve ser cíclico de qualquer maneira.

Experimente online!

->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 salvos devido a @MartinEnder .}

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

Função anônima. Pega uma lista aninhada como entrada (com base em 1) e retorna Trueou Falsecomo saída. A principal solução aqui é o de 46 bytes #~IsomorphicGraphQ~TransitiveReductionGraph@#&, que testa se um determinado gráfico é isomórfico à sua redução transitiva. O restante converte a entrada em um Graphobjeto.

CJam (41 bytes)

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

Demonstração online , equipamento de teste

Dissecação

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)

Gelatina, 20 bytes

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

Usa indexação baseada em 1. Experimente online!

Visão geral frouxa

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