210. Course Schedule II

📝 Problem Details

• Title: 210. Course Schedule II
• Link: https://leetcode.com/problems/course-schedule-ii/
• Difficulty: Medium
• Tags/Categories: Graphs DFS BFS Topological-Sort DAG

💭What Were My Initial Thoughts?

- treat each pair in prerequisites as a connected edge between two nodes
	- connection = second val --> first val
- there are numCourses nodes, but not every vertex needs to have an edge
- we need to construct an adjacency list baesd on the prerequisites provided
- perform a DFS on the graph with the constructed adj list
	- if any cycles are located , return an empty array early as its impossible to complete all courses
	- perform topological sort 

🤔What Did I Struggle With?

unfamiliar with algorithm for topological sort

💡 Explanation of Solution

• Treat each course as a node in a directed graph

• Each prerequisite pair [A,B] forms a directed edge from B --> A (meaning B must be taken before A)

• Some courses may not have any prerequisites, meaning they will not have any incoming edges

• The problem can be solved using Topological Sorting of a Directed Acyclic Graph (DAG)

• Build the Graph:

  • Construct an adjacency list where prerequisites[i] = [A, B] means B → A.

• DFS for Cycle Detection & Topological Sorting:

  • Maintain a visited[] array:
    • 0 → Unvisited
    • 1 → Visiting (on current DFS path)
    • 2 → Processed (safe)
  • If we encounter a node already marked 1, a cycle exists, and we return [].
  • Otherwise, perform DFS and add nodes to a stack after processing.

• Extract Course Order:

  • The stack contains the nodes in reverse topological order.
  • Pop elements from the stack to get the correct order.

⌛ Complexity Analysis

Time Complexity: O(V + E)
Space Complexity: (V + E)

---

💻 Implementation of Solution (DFS)

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adjList(numCourses);
        vector<int> visited(numCourses, 0);
        stack<int> courseStack;
        vector<int> result;
 
        // build adjList
        for(const auto& prereq : prerequisites) {
            int course = prereq[0];
            int pre = prereq[1];
            adjList[pre].push_back(course); // B-->A (pre --> course)
        }
 
        // perform dfs for cycle detection / topological sort
        for(int i=0; i < numCourses; i++) {
            if(visited[i] == 0) { // if unvisited
                if(hasCycle(i, adjList, visited, courseStack)) return {}; // cycle detected
            }
        }
 
        // extract topological order
        while(!courseStack.empty()) {
            result.push_back(courseStack.top());
            courseStack.pop();
        }
        return result;
    }
 
    bool hasCycle(int node, vector<vector<int>>& adjList, vector<int>& visited, stack<int>& courseStack) {
        if(visited[node] == 1) return true; // cycle detected
        if(visited[node] == 2) return false; // already processed (safe)
 
        visited[node] = 1; // mark as visiting (currently on stack)
 
        for(int neighbour : adjList[node]) {
            if(hasCycle(neighbour, adjList, visited, courseStack)) {
                return true;
            }
        }
 
        visited[node] = 2; // mark as processed
        courseStack.push(node); // push to stack for topological sorting
        return false;
    }
};

Alternate Approach (BFS)

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        // Build the graph and compute in-degrees.
        vector<vector<int>> adjList(numCourses);
        vector<int> indegree(numCourses, 0);
        
        for (const auto& p : prerequisites) {
            int course = p[0];
            int pre = p[1];
            // Edge: pre --> course.
            adjList[pre].push_back(course);
            indegree[course]++;
        }
        
        // Initialize the queue with nodes that have in-degree 0.
        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0)
                q.push(i);
        }
        
        // Process nodes.
        vector<int> order;
        while (!q.empty()) {
            int node = q.front();
            q.pop();
            order.push_back(node);
            
            // Reduce the in-degree for each neighbor.
            for (int neighbor : adjList[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0)
                    q.push(neighbor);
            }
        }
        
        // If not all nodes are processed, a cycle exists.
        if (order.size() != numCourses)
            return {};
        
        return order;
    }
};