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.
Sifat 2: Terdapat dua jenis node, yang merupakan anggota dari cycle dan yang menuju ke suatu cycle
Perhatikan gambar berikut. node berwarna merah merupakan anggota dari cycle, sementara yang berwarna putih adalah anggota dari node yang menuju ke suatu cycle.
Apabila kita menelusuri grafnya dari sembarang node, dijamin kita akan sampai di suatu cycle.
Sifat 3: Setiap cycle pasti terisolasi dengan cycle lainnya
Supaya sebuah node dapat menjangkau lebih dari satu cycle, diharuskan ada node yang bercabang. Namun ini tidak mungkin terjadi karena setiap node memiliki tepat satu keluaran, artinya tidak ada node yang bercabang.Dengan demikian struktur graf pasti terdiri dari kelompok-kelompok cycle yang terisolasi; tidak mungkin suatu node menjadi anggota dari lebih dari 1 cycle.
Sifat 4: Jika terdapat N node, maka dijamin terdapat maksimum O(N) cycle
Dari sifat sebelumnya, dipelajari bahwa tidak mungkin suatu node menjadi anggota dari lebih dari 1 cycle. Artinya cycle terbanyak yang dapat dihasilkan dibatasi oleh banyaknya node. Sebagai catatan, cycle paling banyak dapat dihasilkan dengan setiap node menunjuk ke dirinya sendiri.Memanfaatkan Sifat-Sifatnya
Manfaatnya akan terasa saat menghadapi soal dengan graf berciri seperti ini. Misalnya dengan menyadari bahwa setiap node akan berakhir pada suatu cycle. Bisa juga dengan mendekomposisi graf menjadi beberapa kelompok cycle, lalu menyelesaikan setiap kelompok cycle secara independen.Sebagai contoh, perhatikan soal berikut:
Pak Dengklek memiliki N bebek, dinomori dari 1 sampai dengan N. Setiap bebek memiliki tepat seekor bebek lainnya sebagai sahabat karibnya. Bebek mungkin saja menganggap dirinya sebagai sahabat, artinya bebek tersebut narsis.
Pak Dengklek akan memberi cokelat kepada bebek ke-P. Karena bebek sangat setiakawan dengan sahabat karibnya, ia akan memberikan cokelat itu kepada sahabat karibnya. Tentu saja bebek yang menerima cokelat ini akan meneruskan cokelat tersebut ke sahabat karibnya lagi, membentuk rangkaian peristiwa beri-memberi yang mungkin tiada akhirnya.
Pak Dengklek ingin tahu, pada peristiwa beri-memberi yang ke-K, bebek nomor berapa yang menerima cokelat tersebut?
Batasan:
1 ≤ N ≤ 100.000
1 ≤ P ≤ N
1 ≤ K ≤ 2.000.000.000
Contoh Solusi
Struktur sahabat karib ini membentuk graf yang baru dibahas. Solusi naif dengan mensimulasikan peristiwa beri-memberi sebanyak K kali memiliki kompleksitas O(K), terlalu lambat dan akan mendapat Time Limit Exceeded.
Manfaatkan observasi bahwa suatu saat, cokelat akan “terperangkap” dalam suatu cycle.
Ketika hal ini terjadi, kita dapat menggunakan sisa bagi banyaknya beri-memberi yang masih diperlukan terhadap ukuran cycle, untuk mengetahui bebek mana yang mendapatkan cokelat pada akhirnya.
Dengan penelusuran graf DFS, cycle dijamin dicapai dalam O(N) langkah. Ukuran cycle dapat dicari dalam O(N) juga. Setelah itu mencari sisa bagi dapat dilakukan dalam O(1). Solusi ini bekerja dalam O(N). Perhatikan juga kasus khusus ketika peristiwa beri-memberi telah berlangsung K kali sebelum cycle ditemui.
Penutup
Saya harap kini kalian menjadi lebih siap memulai analsis ketika menghadapi graf ini. Oh ya, sepertinya jenis graf ini merupakan yang paling saya sukai.
Untuk kasus yang lebih umum, yaitu ketika setiap node dapat memiliki sembarang keluaran, dekomposisi cycle perlu dilakukan dengan algoritma pencarian Strongly Connected Component (SCC). Selain itu, banyaknya cycle menjadi eksponensial terhadap N.
Tidak ada komentar :
Posting Komentar