Jumat, 29 November 2019

Graf Berarah dengan Setiap Node Memiliki Tepat Satu Keluaran

Graf merupakan konsep yang umum ditemui pada kompetisi pemrograman. Kali ini kita akan membahas graf dengan sifat yang menarik, yaitu setiap node-nya memiliki tepat satu keluaran (memiliki tepat 1 outdegree).

Kalau digambar, grafnya terlihat seperti ini:




Sifat 1: Dijamin terdapat cycle

Tidak mungkin kita dapat membentuk grafnya tanpa cycle. Jika terdapat N node, maka usaha terbaik yang dapat kita lakukan untuk menghindari cycle adalah membentuk struktur seperti rantai: setiap node menunjuk ke node lainnya. Sayangnya ujung terakhir dari struktur rantai ini harus menunjuk ke suatu node lainnya, yang mana pilihannya adalah node-node sebelumnya. Hal ini menjamin selalu terbentuk setidaknya sebuah cycle.