Course Schedule 2 - Task Ordering Using Topological Sort

There are N tasks, labeled from 0 to N-1. Some tasks have prerequisites, meaning a task must be done only after another task is completed. These dependencies are given as pairs [a, b] meaning b must be done before a.

The goal is to return an ordering of tasks that satisfies all the prerequisites. If no valid ordering exists (due to a cycle), return an empty array.

This is a classic case of Topological Sorting in a Directed Graph.

Understanding the Problem

You are given an integer numCourses, which represents the total number of courses labeled from 0 to numCourses - 1. You are also given a list of prerequisite pairs prerequisites, where each pair [a, b] means that you must complete course b before course a.

Your goal is to determine a valid order to take all the courses, such that the prerequisites are respected. If there’s no way to complete all courses due to circular dependencies (cycles), you should return an empty array.

Step-by-Step Solution with Example

Step 1: Represent the problem as a directed graph

Each course is a node. Each prerequisite pair [a, b] becomes a directed edge from b → a. This means course b must come before a.

Step 2: Build the adjacency list and indegree array

The adjacency list keeps track of all courses that depend on a course. The indegree array counts how many prerequisites each course has.

Input:
numCourses = 4,
prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]

Adjacency List:
0 → [1, 2]
1 → [3]
2 → [3]

Indegree:
[0, 1, 1, 2]

Step 3: Initialize the queue with courses that have zero prerequisites

We can start with courses that have indegree 0 because they don’t depend on any other course.

In this example, course 0 has no prerequisites, so we begin with queue = [0].

Step 4: Perform topological sort using Kahn’s Algorithm

We repeat the following:

• Pop a course from the queue
• Add it to the result list
• Reduce the indegree of all its neighbors
• If any neighbor’s indegree becomes 0, add it to the queue

Process:
queue = [0]         → result = []
take 0              → result = [0]
decrease indegree of 1 → indegree[1] = 0 → add 1 to queue
decrease indegree of 2 → indegree[2] = 0 → add 2 to queue

queue = [1, 2]
take 1              → result = [0, 1]
decrease indegree of 3 → indegree[3] = 1

take 2              → result = [0, 1, 2]
decrease indegree of 3 → indegree[3] = 0 → add 3 to queue

take 3              → result = [0, 1, 2, 3]

Step 5: Verify result length

If the result contains all numCourses (i.e., length equals numCourses), we have found a valid order. If not, it means there was a cycle.

Edge Cases

• No prerequisites: If the list is empty, all courses can be taken in any order. For example, numCourses = 3, prerequisites = [] → possible result: [0, 1, 2].
• Cycle in prerequisites: Example [[1, 0], [0, 1]] forms a cycle. No course order is valid. Return [].
• Disconnected components: Example [[1, 0], [3, 2]]. These are independent chains and can be solved separately. Valid result: [0, 1, 2, 3] or [2, 3, 0, 1].

Finally

This problem is a classic example of topological sorting in a directed graph. Kahn’s Algorithm is an efficient way to build the course order using a queue and indegree tracking. Always ensure to handle cycles and special cases like no prerequisites or disconnected graphs.

Practicing this problem strengthens your understanding of graph algorithms and helps you apply them in scheduling and dependency resolution scenarios.

1. Initialize an adjacency list graph and an array indegree to count prerequisites for each node.
2. Fill the graph and indegree based on given prerequisites.
3. Initialize a queue with nodes having indegree = 0.
4. While the queue is not empty:
1. Pop a node from the queue and add it to the result list.
2. For each neighbor, decrement its indegree.
3. If indegree becomes 0, enqueue the neighbor.
5. If the result list contains all tasks, return it. Otherwise, return an empty array.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int graph[MAX][MAX], indegree[MAX], queue[MAX];
int front = 0, rear = -1;

void enqueue(int v) { queue[++rear] = v; }
int dequeue() { return queue[front++]; }

void topologicalSort(int numTasks, int prerequisites[][2], int prereqSize) {
    for (int i = 0; i < prereqSize; i++) {
        int a = prerequisites[i][0];
        int b = prerequisites[i][1];
        graph[b][a] = 1;
        indegree[a]++;
    }
    
    for (int i = 0; i < numTasks; i++)
        if (indegree[i] == 0)
            enqueue(i);

    int count = 0;
    while (front <= rear) {
        int curr = dequeue();
        printf("%d ", curr);
        count++;
        for (int i = 0; i < numTasks; i++) {
            if (graph[curr][i] && --indegree[i] == 0)
                enqueue(i);
        }
    }

    if (count != numTasks)
        printf("\nCycle detected. No valid ordering.\n");
}

int main() {
    int prerequisites1[][2] = {{1,0},{2,0},{3,1},{3,2}};
    topologicalSort(4, prerequisites1, 4);
    printf("\n");
    int prerequisites2[][2] = {{0,1},{1,0}};
    topologicalSort(2, prerequisites2, 2);
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> findOrder(int numTasks, vector<pair<int, int>>& prerequisites) {
    vector<vector<int>> graph(numTasks);
    vector<int> indegree(numTasks, 0);

    for (auto& [a, b] : prerequisites) {
        graph[b].push_back(a);
        indegree[a]++;
    }

    queue<int> q;
    for (int i = 0; i < numTasks; i++)
        if (indegree[i] == 0)
            q.push(i);

    vector<int> order;
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        order.push_back(curr);
        for (int next : graph[curr])
            if (--indegree[next] == 0)
                q.push(next);
    }

    return (order.size() == numTasks) ? order : vector<int>{};
}

int main() {
    vector<pair<int, int>> prerequisites1 = {{1,0},{2,0},{3,1},{3,2}};
    vector<int> order1 = findOrder(4, prerequisites1);
    for (int x : order1) cout << x << " ";
    cout << endl;

    vector<pair<int, int>> prerequisites2 = {{0,1},{1,0}};
    vector<int> order2 = findOrder(2, prerequisites2);
    if (order2.empty()) cout << "No valid ordering\n";
    return 0;
}

from collections import deque, defaultdict

def find_order(num_tasks, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * num_tasks

    for a, b in prerequisites:
        graph[b].append(a)
        indegree[a] += 1

    queue = deque([i for i in range(num_tasks) if indegree[i] == 0])
    order = []

    while queue:
        curr = queue.popleft()
        order.append(curr)
        for neighbor in graph[curr]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == num_tasks else []

print(find_order(4, [[1,0],[2,0],[3,1],[3,2]]))
print(find_order(2, [[0,1],[1,0]]))

import java.util.*;

public class TaskScheduler {
    public static List<Integer> findOrder(int numTasks, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        int[] indegree = new int[numTasks];
        for (int i = 0; i < numTasks; i++) graph.add(new ArrayList<>());

        for (int[] pair : prerequisites) {
            graph.get(pair[1]).add(pair[0]);
            indegree[pair[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numTasks; i++) if (indegree[i] == 0) queue.add(i);

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            result.add(curr);
            for (int neighbor : graph.get(curr))
                if (--indegree[neighbor] == 0)
                    queue.add(neighbor);
        }
        return result.size() == numTasks ? result : new ArrayList<>();
    }

    public static void main(String[] args) {
        System.out.println(findOrder(4, new int[][]{{1,0},{2,0},{3,1},{3,2}}));
        System.out.println(findOrder(2, new int[][]{{0,1},{1,0}}));
    }
}

function findOrder(numTasks, prerequisites) {
  const graph = Array.from({ length: numTasks }, () => []);
  const indegree = Array(numTasks).fill(0);

  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    indegree[a]++;
  }

  const queue = [];
  for (let i = 0; i < numTasks; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  const result = [];
  while (queue.length > 0) {
    const task = queue.shift();
    result.push(task);
    for (const neighbor of graph[task]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === numTasks ? result : [];
}

console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]));
console.log(findOrder(2, [[0,1],[1,0]]));

package main

import (
    "fmt"
)

func findOrder(numTasks int, prerequisites [][]int) []int {
    graph := make([][]int, numTasks)
    indegree := make([]int, numTasks)

    for _, pair := range prerequisites {
        a, b := pair[0], pair[1]
        graph[b] = append(graph[b], a)
        indegree[a]++
    }

    queue := []int{}
    for i := 0; i < numTasks; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    result := []int{}
    for len(queue) > 0 {
        curr := queue[0]
        queue = queue[1:]
        result = append(result, curr)
        for _, neighbor := range graph[curr] {
            indegree[neighbor]--
            if indegree[neighbor] == 0 {
                queue = append(queue, neighbor)
            }
        }
    }

    if len(result) == numTasks {
        return result
    }
    return []int{}
}

func main() {
    fmt.Println(findOrder(4, [][]int{{1,0},{2,0},{3,1},{3,2}}))
    fmt.Println(findOrder(2, [][]int{{0,1},{1,0}}))
}

use std::collections::VecDeque;

fn find_order(num_tasks: usize, prerequisites: Vec<(usize, usize)>) -> Vec<usize> {
    let mut graph = vec![vec![]; num_tasks];
    let mut indegree = vec![0; num_tasks];

    for (a, b) in prerequisites {
        graph[b].push(a);
        indegree[a] += 1;
    }

    let mut queue: VecDeque<usize> = (0..num_tasks).filter(|&i| indegree[i] == 0).collect();
    let mut result = vec![];

    while let Some(curr) = queue.pop_front() {
        result.push(curr);
        for &neighbor in &graph[curr] {
            indegree[neighbor] -= 1;
            if indegree[neighbor] == 0 {
                queue.push_back(neighbor);
            }
        }
    }

    if result.len() == num_tasks {
        result
    } else {
        vec![]
    }
}

fn main() {
    println!("{:?}", find_order(4, vec![(1,0),(2,0),(3,1),(3,2)]));
    println!("{:?}", find_order(2, vec![(0,1),(1,0)]));
}

fun findOrder(numTasks: Int, prerequisites: Array<IntArray>): List<Int> {
    val graph = Array(numTasks) { mutableListOf<Int>() }
    val indegree = IntArray(numTasks)
    for ((a, b) in prerequisites) {
        graph[b].add(a)
        indegree[a]++
    }
    val queue = ArrayDeque<Int>()
    for (i in 0 until numTasks) if (indegree[i] == 0) queue.add(i)

    val result = mutableListOf<Int>()
    while (queue.isNotEmpty()) {
        val curr = queue.removeFirst()
        result.add(curr)
        for (next in graph[curr]) {
            indegree[next]--
            if (indegree[next] == 0) queue.add(next)
        }
    }
    return if (result.size == numTasks) result else emptyList()
}

fun main() {
    println(findOrder(4, arrayOf(intArrayOf(1,0), intArrayOf(2,0), intArrayOf(3,1), intArrayOf(3,2))))
    println(findOrder(2, arrayOf(intArrayOf(0,1), intArrayOf(1,0))))
}

func findOrder(_ numTasks: Int, _ prerequisites: [[Int]]) -> [Int] {
    var graph = Array(repeating: [Int](), count: numTasks)
    var indegree = Array(repeating: 0, count: numTasks)

    for pair in prerequisites {
        let a = pair[0], b = pair[1]
        graph[b].append(a)
        indegree[a] += 1
    }

    var queue = [Int]()
    for i in 0..<numTasks {
        if indegree[i] == 0 { queue.append(i) }
    }

    var result = [Int]()
    while !queue.isEmpty {
        let curr = queue.removeFirst()
        result.append(curr)
        for neighbor in graph[curr] {
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0 { queue.append(neighbor) }
        }
    }
    return result.count == numTasks ? result : []
}

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))
print(findOrder(2, [[0,1],[1,0]]))

function findOrder(numTasks: number, prerequisites: number[][]): number[] {
  const graph: number[][] = Array.from({ length: numTasks }, () => []);
  const indegree: number[] = Array(numTasks).fill(0);

  for (const [a, b] of prerequisites) {
    graph[b].push(a);
    indegree[a]++;
  }

  const queue: number[] = [];
  for (let i = 0; i < numTasks; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  const result: number[] = [];
  while (queue.length > 0) {
    const task = queue.shift()!;
    result.push(task);
    for (const neighbor of graph[task]) {
      indegree[neighbor]--;
      if (indegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  return result.length === numTasks ? result : [];
}

console.log(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]));
console.log(findOrder(2, [[0,1],[1,0]]));

Time complexity

Space complexity

O(V + E)

We use space for the adjacency list (O(E)), the indegree array (O(V)), the queue (up to O(V)), and the result list (O(V)).