Melakukan DFS bisa mahal, dan melakukan N kali DFS bisa melelahkan, tetapi hal yang perlu diingat adalah pemangkasan. Dalam masalah ini, kami memiliki kondisi yang sangat bagus bahwa kami melakukan DFS jika dan hanya jika kursus saat ini belum diproses sebelumnya. Ternyata rata-rata ini akan tetap linier, mungkin waktu eksekusi 2N (N=10^5), tetapi masih bisa dilakukan. Maka triknya adalah memiliki 3 hashtable: 1/ mata kuliah yang telah diambil, 2/ daftar mata kuliah –> prasyarat dan 3/ daftar mata kuliah –> syarat akhir. Kemudian panggil DFS untuk setiap node, dan periksa apakah semua telah dikunjungi. Kode ada di bawah, sorak-sorai dan Selamat Hari MLK!!! ACC
207. Jadwal Kursus
Sedang
Ada total numCourses kursus yang harus Anda ambil, berlabel dari 0 ke numCourses - 1. Anda diberi array prerequisites di mana prerequisites[i] = [ai, bi] menunjukkan bahwa Anda harus mengambil kursus bi dulu kalo mau ikut kursus ai.
- Misalnya pasangan
[0, 1], menunjukkan bahwa untuk mengambil kursus0kamu harus mengambil kursus terlebih dahulu1.
Kembali true jika Anda dapat menyelesaikan semua kursus. Jika tidak, kembalikan false.
Contoh 1:
Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Contoh 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Kendala:
1 <= numCourses <= 1050 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCourses- Semua prasyarat pasangan[i] adalah unik.
public bool CanFinish(int numCourses, int[][] prerequisites)
{
Hashtable htPre = new Hashtable();
Hashtable htPos = new Hashtable();
for (int i = 0; i
