Olimpiade Sains Kota (OSK) 2018 - Komputer, Nomor 22

  Paraler artinya bisa dikerjakan bersamaan.

kursus pertama, Pak Dengklek(D) bisa mengikuti C1 dan C13 untuk kursus pertama

kursus kedua, karna sudah melalui C1 dan C13, Pak D bisa mengikuti C4 dari C13 (tidak bisa langsung ke C14 karna tidak ad panah dari C14 ke C4), Pak D juga bisa mengikuti C2 dari C1 dengan alasan yang sama seperti tadi.

kursus ketiga, pak D akhirnya bisa mengikuti C14 setelah mengikuti C4.

kursus keempat, Pak D bisa mengikuti C3 dari C2, dan C5 dari C14, jadi pada kursus ini pak D mengikuti C3 dan C5.

kursus kelima, pak D bisa mengikuti C8 dari C5.Pak d juga bisa mengikuti C9,C6, dan C10. jadi pada kursus ini pak D mengikuti C8, C6, C9, dan C10.

kursus keenam, setelah mengikuti C8 pak D sudah tidak mengikuti kursus lain, jadi kita mulai fokus ke C10 yang sudah dilalui pak D. setelah mengikuti C10, pak D akhirnya bisa mengikuti C7 dan C11

kursus ketujuh, setelah mengikuti C11 pak D mengikuti C12, dan setelah C12 pak D sudah tidak mengikuti kursus lagi

Jadi, totalnya Pak Dengklek mengikuti 7 kursus, yang bila dihitung lama waktunya maka 7*3 = 21 bulan.

Sinii sama Om 

Solusi : Topological Sorting

Definisi 1 :
in_degree(v) = banyaknya kursus sebelum kursus v sehingga setelah kursus-kursus itu, mungkin saja dapat melanjutkan ke kursus v

Algoritma :
1. Buat sebuah antrian yang memuat nama kursus
2. Untuk setiap kursus x yang in_degree(x)-nya bernilai nol, masukkan x ke dalam antrian
3. Setiap kursus yang dapat diikuti setelah mengikuti kursus x (x di dalam antrian), buang x, buang jalur dari kursus x ke kursus yang berikutnya
4. Jika semua kursus sudah diikuti alias antriannya sudah kosong, berhenti. Jika antrian belum kosong, ulangi langkah ke-2

Waktu = 0 bulan, jika antrian terisi, waktu akan bertambah 3 bulan
Antrian : [ ] (kosong)
Kursus yang bisa diikuti Pak Dengklek adalah C1 dan C13, karena in_degree(C1) dan in_degree(C13) adalah nol.
Hapus jalur (C1, C2); (C1, C3); (C1, C4); (C13, C4); dan (C13, C14)
Antrian : [C1, C13], waktu = 3 bulan
Hapus kursus C1 dan C13

Antrian : [ ]
Masukkan C2, C4 dalam antrian, karena in_degree(C2) dan in_degree(C4) adalah nol.
Hapus jalur (C4, C14); dan (C2, C3)
Antrian : [C2, C4], waktu = 6 bulan
Hapus kursus C2 dan C4

Antrian : [ ]
Masukkan C14 ke dalam antrian, karena in_degree(C14) adalah nol.
Hapus jalur (C14, C3); dan (C14, C5)
Antrian : [C14], waktu = 9 bulan
Hapus kursus C14

Antrian : [ ]
Masukkan C3, C5 dalam antrian, karena in_degree(C3) dan in_degree(C5) adalah nol.
Hapus jalur (C3, C6); (C3, C7); (C3, C9); (C3, C10); dan (C5, C8)
Antrian : [C3, C5], waktu = 12 bulan
Hapus kursus C3 dan C5

Antrian : [ ]
Masukkan C12 dalam antrian
Masukkan C6, C8, C9, dan C10 dalam antrian, karena in_degree(C6), in_degree(C8), in_degree(C9), dan in_degree(C10) adalah nol.
Hapus jalur (C10, C7) dan (C10, C11)
Antrian : [C6, C8, C9, C10], waktu = 15 bulan
Hapus kursus C6, C8, C9, dan C10

Antrian : [ ]
Masukkan C11 dalam antrian, karena in_degree(C11) adalah nol.
Hapus jalur (C11, C12)
Antrian : [C11], waktu = 18 bulan
Hapus kursus C11

Antrian : [ ]
Masukkan C12 dalam antrian, karena in_degree(C12) adalah nol.
Antrian : [C12], waktu = 21 bulan
Habus kursus C12
Seluruh kursus telah diikuti, algoritma berhenti

Jawab : 21 bulan

Jika ada kesalahan lagi, mohon koreksinya :')