מריה בוטוסוב

לבדוק האם אפשר לבנות מערכת של קורסים.

public bool CanFinish(int numCourses, int[][] prerequisites) {
    int count = 0;
    Queue<int> q = new Queue<int>();
    int[] dependsOnMe = new int[numCourses];
    List<int>[] predecessors = new List<int>[numCourses];
        
    foreach(var p in prerequisites) {
        int currentCourse = p[1];
        int predecessor = p[0];
        if(predecessors[currentCourse] == null)
            predecessors[currentCourse] = new List<int>();
        predecessors[currentCourse].Add(predecessor);
        dependsOnMe[predecessor]++;
    }
        
    //first - take independent courses
    for(int i=0;i<numCourses;i++){
        if(dependsOnMe[i]==0)
            q.Enqueue(i);
    }
        
    while(q.Count>0){
        int course = q.Dequeue();
        count++;
        foreach(var predecessor in predecessors[course]??new List<int>()) {
            dependsOnMe[predecessor]--;
            if(dependsOnMe[predecessor] == 0)
                q.Enqueue(predecessor);
        }
    }
    return count == numCourses;        
}