Leetcode 207 Course Schedule
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.
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.
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.
- Soruda bize kurs sayısı ve bu kursların ön koşullarının olduğu bir liste veriliyor.Bazı kursları almak için önce ön koşulu olan kursu almak lazım.Tüm kursları alabiliyorsak True alamıyorsak False dönmemiz isteniyor.
- Tüm kursları alamama durumunu sağlayan şey [[1,0],[0,1]] görüldüğü gibi iki kursun birbirinin ön koşulu olup bir döngüye girmesi sonucu oluşur.
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
#ilk olarak preMap adında tüm kurslar için ön koşul listesi boş bir dict oluştururuz.
preMap = {i:[] for i in range(numCourses)}
#daha sonra bu dict doldururuz.Artık hangi kursun ön koşulunun hangi kurs olduğunu biliyoruz.
for crs,pre in prerequisites:
preMap[crs].append(pre)
#şimdi yapacağımız şey visitSet adında ziyaret ettiğimiz kursları koyacağımız bir set()
#bu sayede aynı kursu gördüğümüzde bir döngü olduğunu anlayıp False dönebiliriz
visitSet = set()
#dfs ana fonksiyonu yazalım
def dfs(crs):
#eğer kurs daha önce ziyaret edildi ise False dön
if crs in visitSet:
return False
#eğer kursun bir ön koşul kursu yok ise True dön
if preMap[crs] == []:
return True
#kursu ziyaret edilenlere ekle
visitSet.add(crs)
#kursun ön koşul kursları için dfs fonksiyonunu çağır
for pre in preMap[crs]:
#eğer dfs false dönüyor ise direk false dön
if not dfs(pre):return False
#kursu ziyaret edilmiş kurslardan çıkar
visitSet.remove(crs)
#bu kurs ile ilgili daha sonraki işlemlerin daha hızlı olması için önkoşul kurslarını boşalt
preMap[crs]=[]
return True
#listedeki tüm kurslar için dfs fonksiyonunu çağır herhangi biri false alır ise direk false dön
for crs in range(numCourses):
if not dfs(crs):return False
return True