Целью этой задачи является конечно- ориентированный ациклический граф (DAG), определить, является ли граф транзитивной редукцией .

Краткое объяснение того, что такое DAG и переходные сокращения:

DAG - это граф с направленными ребрами (то есть вы можете перемещаться только в одном направлении по этому ребру), так что при наличии любого начального узла на графике невозможно вернуться к начальному узлу (то есть циклов нет).

Для любого начального узла, если возможно перейти к другому конечному узлу в графе через любое произвольное положительное число ребер, то этот конечный узел определяется как достижимый из начального узла. В общей группе обеспечения доступности баз данных может быть несколько путей, которые могут быть взяты от начального узла к целевому конечному узлу. Например, возьмите этот граф алмазов:

Чтобы добраться до узла Dс A, вы могли бы пойти по пути A->B->Dили A->C->D. Таким образом, Dдостижимо из A. Однако нет пути, по которому можно добраться до узла, Bначиная с узла C. Таким образом, узел Bне доступен с узла C.

Определите достижимость графа как список достижимых узлов для каждого начального узла в графе. Таким образом, для того же примера алмазного графика достижимость:

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

Другой график, который имеет ту же достижимость, что и приведенный выше график, показан ниже:

Однако этот второй граф имеет больше ребер, чем исходный граф. Транзитивная редукция графа - это граф с наименьшим числом ребер и такой же достижимостью исходного графа. Таким образом, первый граф является транзитивной редукцией второго.

Для конечного DAG транзитивное сокращение гарантированно существует и является уникальным.

вход

Входные данные представляют собой «список списков», где внешний список имеет длину числа вершин, а каждый внутренний список - длину числа ребер, покидающих связанный узел, и содержит индексы узлов назначения. Например, один из способов описать первый график выше (при условии индексации на основе нуля):

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

Вы можете начать индексирование первого узла с любого произвольного целочисленного значения (например, индексация на основе 0 или 1).

Вход может поступать из любого источника входного сигнала (stdio, параметр функции и т. Д.). Вы можете выбрать точный формат ввода, если дополнительная информация не указана. Например, если вы хотите получить входные данные из stdio, каждая строка может быть списком ребер для связанного узла. Напр .:

1 2
3
3
'' (blank line)

Индексы в каждом списке смежности не обязательно сортируются, и может быть несколько ребер, соединяющих два узла (например:) [[1,1],[]]. Вы можете предположить, что входной граф слабо связан и не содержит циклов (то есть это DAG).

Выход

Вывод верен, если заданная входная группа DAG является транзитивным сокращением, а в противном случае - ложным значением. Это может быть любой желаемый приемник (stdio, возвращаемое значение, выходной параметр и т. Д.)

Примеры

Во всех примерах используется индексация на основе 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

счет

Это код гольф; выигрывает наименьший код в байтах. Ваш код должен завершиться за разумное время (максимум 10 минут на любом оборудовании). Применяются стандартные лазейки. Вы можете использовать любые встроенные модули по желанию.

Рубин, 101 97 байт

Простой подход, который вычисляет охват каждого узла и рассматривает возможность доступа к дочернему узлу через любой из других узлов. Кажется, что на циклических графах происходит сбой, но определение DAG подразумевает, что он не должен быть циклическим в любом случае.

Попробуйте онлайн!

->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 байта

^{13 байтов сохранено благодаря @MartinEnder .}

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

Анонимная функция. Принимает вложенный список как вход (на основе 1) и возвращает Trueили Falseкак вывод. Основным решением здесь является 46-байт #~IsomorphicGraphQ~TransitiveReductionGraph@#&, который проверяет, является ли данный граф изоморфным его транзитивной редукции. Остальное преобразует входные данные в Graphобъект.

CJam (41 байт)

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

Демо-версия , тестовый жгут

рассечение

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)

Желе, 20 байт

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

Использует индексирование на основе 1. Попробуйте онлайн!

Свободный Обзор

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