אפר.22

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

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

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

numberOfCourses = 2, prerequisites = [[1,0],[0,1]]
Result: false

Explanation: Total 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.


  1. public bool CanFinish(int numCourses, int[][] prerequisites) {
  2. int count = 0;
  3. Queue<int> q = new Queue<int>();
  4. int[] dependsOnMe = new int[numCourses];
  5. List<int>[] predecessors = new List<int>[numCourses];
  6. foreach(var p in prerequisites) {
  7. int currentCourse = p[1];
  8. int predecessor = p[0];
  9. if(predecessors[currentCourse] == null)
  10. predecessors[currentCourse] = new List<int>();
  11. predecessors[currentCourse].Add(predecessor);
  12. dependsOnMe[predecessor]++;
  13. }
  14. //first - take independent courses
  15. for(int i=0;i<numCourses;i++){
  16. if(dependsOnMe[i]==0)
  17. q.Enqueue(i);
  18. }
  19. while(q.Count>0){
  20. int course = q.Dequeue();
  21. count++;
  22. foreach(var predecessor in predecessors[course]??new List<int>()) {
  23. dependsOnMe[predecessor]--;
  24. if(dependsOnMe[predecessor] == 0)
  25. q.Enqueue(predecessor);
  26. }
  27. }
  28. return count == numCourses;
  29. }


תגיות:
שתף את הסיפור הזה:

תגובות(0)

השאירו תגובה

קפטצ'ה לא מתאימה

תגובה