Course Schedule II

class Solution {
public:
    vector<int> sortCourses(int totalCourses, vector<vector<int>>& deps) {
        map<int, list<int>> graph;
        vector<int> inDegrees(totalCourses, 0);
        vector<int> courseOrder;

        // Building the graph
        for (const auto& dep : deps) {
            int course = dep[0];
            int prerequisite = dep[1];
            graph[prerequisite].push_back(course);
            inDegrees[course]++;
        }

        // Queue for courses with no prerequisites
        queue<int> coursesQueue;
        for (int i = 0; i < totalCourses; i++) {
            if (inDegrees[i] == 0) {
                coursesQueue.push(i);
            }
        }

        // Processing the graph
        while (!coursesQueue.empty()) {
            int currentCourse = coursesQueue.front();
            coursesQueue.pop();
            courseOrder.push_back(currentCourse);

            if (graph.count(currentCourse)) {
                for (int neighbor : graph[currentCourse]) {
                    inDegrees[neighbor]--;
                    if (inDegrees[neighbor] == 0) {
                        coursesQueue.push(neighbor);
                    }
                }
            }
        }

        // Check if we could sort all courses
        if (courseOrder.size() == totalCourses) {
            return courseOrder;
        }

        return vector<int>();
    }
};

This solution addresses the problem of scheduling courses given their dependencies, determining a possible order of courses such that all prerequisites are taken before a course. Implemented in C++, the method sortCourses takes the totalCourses and their dependencies deps as parameters and returns a vector of courses in the possible order they should be taken.

• Starts by establishing a graph (map<int, list<int>>) to represent the dependencies and a vector (inDegrees) to maintain the count of prerequisites for each course.
• Builds the graph using input deps where each dependency [course, prerequisite] increases the in-degree of course and maps prerequisite to course in the graph.
• Initializes a queue to store the courses having no prerequisites using the inDegrees vector.
• Processes the courses in order:
  • Removes a course from the queue, adds it to courseOrder.
  • Checks its neighbors (dependent courses), decrements their in-degree, and if any dependent courses no longer have prerequisites, they are added to the queue.
• Finally, checks if all courses have been processed (the size of courseOrder should equal totalCourses):
  • If true, returns the courseOrder.
  • Otherwise, returns an empty vector, indicating it's not possible to complete all courses due to circular dependencies or inconsistencies.

The efficient use of graphs, queue, and adjacency list approach ensures that the algorithm can effectively handle the topological sorting of the courses based on dependencies, which is typical in scenarios like course scheduling or project task management where order based on prerequisites or dependencies is crucial.

class Solution {
    public int[] courseSchedule(int totalCourses, int[][] prereqs) {
        Map<Integer, List<Integer>> adjacencyList = new HashMap<>();
        int[] incomingEdges = new int[totalCourses];
        int[] topoSort = new int[totalCourses];

        // Build the graph
        for (int i = 0; i < prereqs.length; i++) {
            int target = prereqs[i][0];
            int prerequisite = prereqs[i][1];
            List<Integer> coursesList = adjacencyList.getOrDefault(prerequisite, new ArrayList<Integer>());
            coursesList.add(target);
            adjacencyList.put(prerequisite, coursesList);

            // Count the number of prerequisites for each course
            incomingEdges[target]++;
        }

        // Queue for the courses with no prerequisites
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < totalCourses; i++) {
            if (incomingEdges[i] == 0) {
                queue.add(i);
            }
        }

        int index = 0;
        // Process each course with no prerequisites in the queue
        while (!queue.isEmpty()) {
            int course = queue.poll();
            topoSort[index++] = course;

            // Reduce the count of incoming edges for all dependent courses
            if (adjacencyList.containsKey(course)) {
                for (int dependentCourse : adjacencyList.get(course)) {
                    incomingEdges[dependentCourse]--;
                    
                    // If no more prerequisites for this course, add to the queue
                    if (incomingEdges[dependentCourse] == 0) {
                        queue.offer(dependentCourse);
                    }
                }
            }
        }

        // If we managed to process all courses
        if (index == totalCourses) {
            return topoSort;
        }

        return new int[0];  // Return an empty array if topological sort is not possible
    }
}

The problem "Course Schedule II" requires determining whether all courses can be completed given a list of prerequisites and, if possible, returning the order in which the courses should be taken. In Java, the solution involves constructing the solution class with a method courseSchedule.

Here's the approach taken:

• Graph Representation: Utilize a hashmap to represent an adjacency list of all courses and their respective prerequisites. Another array manages the count of incoming edges (prerequisites) for each course.

• Graph Construction:

  • Iterate over the prerequisites array, populating the adjacency list and updating the count of incoming prerequisites for each course.

• Topological Sorting:

  • Use a queue to maintain courses with no prerequisites (incoming edges count of zero).
  • Gradually extract courses from the queue, appending them to the result array of course order and simultaneously reducing the prerequisites count for neighboring courses in the adjacency list.
  • For any neighbors that no longer have prerequisites, add them to the queue for subsequent processing.

• Order Determination:

  • If able to process all the courses, meaning the topological sort includes all courses, return the sorted order.
  • If a cycle exists (some courses still have prerequisites unmet after processing), return an empty array signifying that it's impossible to complete all courses due to cyclic dependencies.

This approach ensures that the solution efficiently determines the course order by leveraging topological sorting of a Directed Acyclic Graph (DAG), handling cases of cyclic dependencies explicitly.

from collections import defaultdict, deque

class Scheduler:

    def scheduleCourses(self, totalCourses: int, preReqs: List[List[int]]) -> List[int]:
        graph = defaultdict(list)
        degree = {}
        for course, prerequisite in preReqs:
            graph[prerequisite].append(course)
            degree[course] = degree.get(course, 0) + 1

        zero_degree_queue = deque([i for i in range(totalCourses) if i not in degree])

        course_order = []

        while zero_degree_queue:
            course = zero_degree_queue.popleft()
            course_order.append(course)

            if course in graph:
                for next_course in graph[course]:
                    degree[next_course] -= 1
                    if degree[next_course] == 0:
                        zero_degree_queue.append(next_course)

        return course_order if len(course_order) == totalCourses else []

This Python solution for determining the order of courses based on prerequisites uses the topological sorting of a directed graph, employing Kahn's algorithm.

• First, an adjacency list graph and an in-degree degree dictionary are created from the list of prerequisites preReqs. Each prerequisite pair updates the graph and degree of the subsequent course.
• A queue zero_degree_queue holds all courses that have no prerequisites (i.e., non-leaf nodes in the graph).
• Another list, course_order, is used to store the result — the order of courses to be taken.
• The main loop processes courses from zero_degree_queue, appending them to course_order and decrementing the in-degrees of their dependent courses. When a course’s in-degree reaches zero, it is added to the queue.
• The function finally returns course_order if all the courses are covered; otherwise, it returns an empty list to indicate that the course sequence isn't possible due to cyclic dependencies.

The code is structured using a class Scheduler with a method scheduleCourses that takes totalCourses and a list of prerequisite pairs. This straightforward approach ensures that the prerequisite relations are properly handled, and only valid course sequences are returned.