Urutan Mata Kuliah
Susun urutan mengambil mata kuliah yang memenuhi semua prasyarat.
Di kampus, beberapa mata kuliah punya prasyarat. Algoritma dan Struktur Data harus diambil setelah Dasar Pemrograman, misalnya. Bantu mahasiswa menyusun urutan mengambil semua mata kuliah. Bila ada beberapa pilihan, ambil yang nomornya paling kecil lebih dulu.
Masukan
Baris pertama berisi N (1 sampai 5000) banyaknya mata kuliah dan M (1 sampai 10000) banyaknya prasyarat. Mata kuliah dinomori 1 sampai N. M baris berikutnya berisi A B, artinya A harus diambil sebelum B.
Keluaran
Satu baris berisi urutan semua mata kuliah, dipisah spasi. Setiap saat, ambil mata kuliah bernomor terkecil yang semua prasyaratnya sudah diambil. Bila prasyaratnya saling melingkar sehingga mustahil, tampilkan Tidak mungkin.
Contoh masukan dan keluaran
Contoh 1
Masukan
6 6 1 3 2 3 3 4 1 5 5 4 4 6
Keluaran
1 2 3 5 4 6
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Hitung untuk setiap mata kuliah berapa prasyarat yang belum diambil. Mata kuliah dengan hitungan nol siap diambil.
Petunjuk 2
Simpan yang siap diambil di heap supaya nomor terkecil selalu didahulukan. Setelah mengambil satu mata kuliah, kurangi hitungan setiap mata kuliah yang menjadikannya prasyarat.