Tujuan dari tantangan ini adalah diberikan grafik asiklik terarah terbatas (DAG), tentukan apakah grafik tersebut merupakan reduksi transitif .

Penjelasan singkat tentang apa itu DAG dan reduksi transitif adalah:

DAG adalah grafik dengan tepi terarah (yaitu Anda hanya dapat melakukan perjalanan satu arah di tepi itu) sehingga memberikan titik awal apa pun pada grafik, tidak mungkin untuk kembali ke titik awal (yaitu tidak ada siklus).

Diberikan titik awal apa pun, jika dimungkinkan untuk melakukan perjalanan ke titik akhir lain dalam grafik melalui jumlah tepi positif sembarang, maka titik akhir tersebut dapat dijangkau dari titik awal. Dalam DAG umum, mungkin ada beberapa jalur yang bisa diambil dari titik awal ke titik akhir target. Misalnya, ambil grafik berlian ini:

Untuk sampai ke node Ddari A, Anda bisa mengambil jalur A->B->Datau A->C->D. Dengan demikian, Ddapat dijangkau dari A. Namun, tidak ada jalur yang bisa diambil untuk menuju ke simpul Bmulai dari simpul C. Dengan demikian, simpul Btidak dapat dijangkau dari simpul C.

Tetapkan jangkauan grafik sebagai daftar simpul yang dapat dijangkau untuk setiap simpul awal dalam grafik. Jadi untuk contoh grafik intan yang sama, jangkauannya adalah:

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

Grafik lain yang memiliki jangkauan yang sama dengan grafik di atas ditunjukkan di bawah ini:

Namun, grafik kedua ini memiliki lebih banyak tepi daripada grafik asli. Reduksi transitif dari grafik adalah grafik dengan jumlah tepi paling sedikit dan jangkauan yang sama dari grafik asli. Jadi grafik pertama adalah reduksi transitif dari yang kedua.

Untuk DAG terbatas, reduksi transitif dijamin ada dan unik.

Memasukkan

Input adalah "daftar daftar", di mana daftar eksternal memiliki panjang jumlah simpul, dan setiap daftar internal adalah panjang dari jumlah tepi yang meninggalkan simpul terkait, dan berisi indeks node tujuan. Misalnya, salah satu cara untuk menggambarkan grafik pertama di atas adalah (dengan asumsi pengindeksan berbasis nol):

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

Anda dapat mulai mengindeks node pertama pada nilai integer sembarang (mis. Pengindeksan berbasis 0 atau 1).

Input dapat berasal dari sumber input yang diinginkan (stdio, parameter fungsi, dll.). Anda bebas memilih format input yang tepat selama tidak ada informasi tambahan yang diberikan. Misalnya, jika Anda ingin mengambil input dari stdio, Anda bisa membuat setiap baris menjadi daftar tepi untuk simpul terkait. Ex.:

1 2
3
3
'' (blank line)

Indeks di setiap daftar adjacency belum tentu diurutkan, dan mungkin ada beberapa sisi yang menghubungkan dua node (mis .:) [[1,1],[]]. Anda dapat mengasumsikan grafik input terhubung dengan lemah , dan tidak mengandung siklus (yaitu, DAG).

Keluaran

Outputnya benar jika input DAG yang diberikan adalah reduksi transitif, dan nilai falsy sebaliknya. Ini mungkin untuk setiap wastafel yang diinginkan (stdio, nilai balik, parameter output, dll.)

Contohnya

Semua contoh menggunakan pengindeksan berbasis 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

Mencetak gol

Ini adalah kode golf; kode terkecil dalam byte menang. Kode Anda harus diselesaikan dalam jumlah waktu yang wajar (maks 10 menit untuk perangkat keras apa pun yang Anda miliki). Celah standar berlaku. Anda dapat menggunakan built-in yang diinginkan.

Ruby, 101 97 byte

Pendekatan sederhana yang menghitung jangkauan dari setiap simpul dan mempertimbangkan apakah simpul anak dapat dicapai melalui salah satu dari simpul lainnya. Tampaknya gagal pada grafik siklik, tetapi definisi DAG menyiratkan bahwa itu tidak boleh siklik.

Cobalah 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 byte

^{13 byte disimpan karena @MartinEnder .}

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

Fungsi anonim. Mengambil daftar bersarang sebagai input (berbasis 1), dan mengembalikan Trueatau Falsesebagai output. Solusi utama di sini adalah 46-byte #~IsomorphicGraphQ~TransitiveReductionGraph@#&, yang menguji apakah grafik yang diberikan adalah isomorfik terhadap reduksi transitifnya. Sisanya mengubah input ke Graphobjek.

CJam (41 byte)

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

Demo online , test harness

Pembedahan

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)

Jelly, 20 byte

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

Menggunakan pengindeksan berbasis 1. Cobalah online!

Ikhtisar longgar

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