LeetCode-Blind-75/210.CourseScheduleII.cs at main · moraouf11/LeetCode-Blind-75 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
public class Solution {
// Topological sort
    public int[] FindOrder(int numCourses, int[][] prerequisites) {
        var preqMap = new Dictionary<int,List<int>>();
        var indegree = new int[numCourses];
        for(int i=0;i<numCourses;i++){
            preqMap[i] = new List<int>();
        }

//[1,0] -> 0 is dependent on 1 , you should finish course zero first, that is represnted by
// { 0, [1] }
// { 1, [] }
        foreach(var prerequisite in prerequisites){
            var course = prerequisite[0];
            var coursePreq = prerequisite[1];
            preqMap[coursePreq].Add(course);

            indegree[course]++;

        }


        Queue<int> queue = new Queue<int>();

        for(int i =0; i<numCourses; i++)
        {
            if(indegree[i]==0)
               queue.Enqueue(i);
        }

        var courseOrder = new int [numCourses];
        int coursesCount=0;

// BFS
        while(queue.Count() != 0)
        {
            int currentCourse = queue.Dequeue();

            courseOrder[coursesCount++] = currentCourse;

            foreach( int preqCourse in preqMap[currentCourse])
            {
                if(--indegree[preqCourse]== 0)
                    queue.Enqueue(preqCourse);
            }

        }

        return coursesCount == numCourses ? courseOrder : new int[0];
    }


        //     var preqMap = new Dictionary<int, List<int>>();
        //     var indegree = new int[numCourses];
        //     for (int i = 0; i < numCourses; i++)
        //     {
        //         preqMap[i] = new List<int>();
        //     }

        //     //[1,0] -> 1 is dependent on 0 , you should finish course zero, that is represnted by
        //     // { 1, [0] }
        //     // { 0, [] }
        //     foreach (var prerequisite in prerequisites)
        //     {
        //         var course = prerequisite[0];
        //         var coursePreq = prerequisite[1];
        //         preqMap[coursePreq].Add(course);

        //         indegree[course]++;

        //     }


        //     Stack<int> queue = new Stack<int>();

        //     for (int i = 0; i < numCourses; i++)
        //     {
        //         if (indegree[i] == 0)
        //             queue.Push(i);
        //     }

        //     var courseOrder = new int[numCourses];
        //     int coursesCount = 0;

        //     while (queue.Count() != 0)
        //     {
        //         int currentCourse = queue.Pop();

        //         courseOrder[coursesCount++] = currentCourse;

        //         foreach (int preqCourse in preqMap[currentCourse])
        //         {
        //             if (--indegree[preqCourse] == 0)
        //                 queue.Push(preqCourse);
        //         }

        //     }

        //     return coursesCount == numCourses ? courseOrder : new int[0];

        // }
}