# Course Schedule - Graph / Directed Graph / Topological Sort

I think the DFS approach is probably just a tiny bit more efficient, but here’s a way to apply Kahn’s Algorithm to determine if there is a cycle. You can track the number of edges that we ‘remove’ and compare that to the total size of the prerequisites list. If there are no cycles, then we should be able to ‘remove’ every edge (removedEdges = prerequisites.length), otherwise, there’s a cycle. Credit: Leetcode

``````public boolean canFinish(int numCourses, int[][] prerequisites) {
if (prerequisites.length == 0) return true;

Map<Integer, List<Integer>> graph = new HashMap<>();

for (int i = 0; i < numCourses; i++) {
graph.put(i, new ArrayList<>());
}

for (int[] prereq : prerequisites) {
}

Map<Integer, Integer> prereqCounts = getPrereqCounts(graph);

Deque<Integer> parents = new ArrayDeque<>();

for (Integer node : prereqCounts.keySet()) {
if (prereqCounts.get(node) == 0)
}

int totalEdges = prerequisites.length;
int removedEdges = 0;

while (!parents.isEmpty()) {
Integer prereq = parents.poll();

for (Integer course : graph.get(prereq)) {
prereqCounts.put(course, prereqCounts.get(course) - 1);
removedEdges++;
if (prereqCounts.get(course) == 0)
}
}

return removedEdges == totalEdges;
}

private Map<Integer, Integer> getPrereqCounts(Map<Integer, List<Integer>> graph) {
Map<Integer, Integer> counts = new HashMap<>();

for (Integer node : graph.keySet()) {
counts.put(node, 0);
}

for (Integer node : graph.keySet()) {
for (Integer child : graph.get(node))
counts.put(child, counts.get(child) + 1);
}

return counts;
}
``````

Hi moderator(s),
I went through the the solution and have no problem understanding it. However, is there any scenarios that force us to use a DFS approach? If yes, can you give an example? Thank you.

the solution marks `dependency.get(1)` as the next node of `dependency.get(0)` in `graph.computeIfAbsent(dependency.get(0), k -> new ArrayList<>()).add(dependency.get(1));` but the question said `For example, [0, 1] means you need to take course 1 before taking course 0` which means dependency.get(0) should be next of dependency.get(1). Does the direction not matter for circular dependency detection?

Because we want to use the Kahn’s Algorithm template from https://algo.monster/problems/topo_intro

Direction matters and the code is consistent with the description.

I can’t think of a scenario… BFS should be fine and easier

For anyone looking for the BFS solution, here it is. The only major differences are in how you initially construct the graph and what you return at the end.

``````from typing import List
from collections import deque

def count_parents(graph):
counts = {course: 0 for course in graph}
for parent, children in graph.items():
for child in children:
counts[child] += 1

return counts

def top_sort(graph):
queue = deque()
result = []

counts = count_parents(graph)
if count == 0:

while queue:
counts[child] -= 1
if counts[child] == 0:
queue.append(child)
return len(result) == len(graph)

def is_valid_course_schedule(n: int, prerequisites: List[List[int]]) -> bool:
graph = {str(i): [] for i in range(n)}
for child, parent in prerequisites:
graph[str(parent)].append(str(child))

``````

My BFS solution…

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

class Solution {
public static boolean isValidCourseSchedule(int n, List<List> prerequisites) {

``````    // Map course -> courses that need to be taken first
Map<Integer, Set<Integer>> graph = buildGraph(n, prerequisites);
Queue<Integer> queue = new ArrayDeque<>();
processIndependentCourses(queue, graph);
while (!queue.isEmpty()) {
int curCourse = queue.remove();
for (Integer curKey : graph.keySet()) {
graph.get(curKey).remove(curCourse);
}

processIndependentCourses(queue, graph);
}

}

private static Map<Integer, Set<Integer>> buildGraph(int n, List<List<Integer>> prerequisites) {

Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++)
map.put(i, new HashSet<>());

for (List<Integer> curPrerequisite : prerequisites) {
}

return map;
}

private static void processIndependentCourses(Queue<Integer> queue, Map<Integer, Set<Integer>> graph) {

List<Integer> independentCourses = graph.keySet().stream().filter(key -> graph.get(key).isEmpty()).collect(Collectors.toList());
independentCourses.forEach(key -> graph.remove(key));
}

public static List<String> splitWords(String s) {
return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
int prerequisitesLength = Integer.parseInt(scanner.nextLine());
List<List<Integer>> prerequisites = new ArrayList<>();
for (int i = 0; i < prerequisitesLength; i++) {
}
scanner.close();
boolean res = isValidCourseSchedule(n, prerequisites);
System.out.println(res);
}
``````

}

My BFS solution, create a Map<Integer, Set> to represent the graph, and modifying it while trying to built a topological sort of it.

At the end I check that the topological sort contains all the n nodes.

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

class Solution {
public static boolean isValidCourseSchedule(int n, List<List> prerequisites) {

``````    // Map course -> courses that need to be taken first
Map<Integer, Set<Integer>> graph = buildGraph(n, prerequisites);
Queue<Integer> queue = new ArrayDeque<>();
processIndependentCourses(queue, graph);
while (!queue.isEmpty()) {
int curCourse = queue.remove();
for (Integer curKey : graph.keySet()) {
graph.get(curKey).remove(curCourse);
}

processIndependentCourses(queue, graph);
}

}

private static Map<Integer, Set<Integer>> buildGraph(int n, List<List<Integer>> prerequisites) {

Map<Integer, Set<Integer>> map = new HashMap<>();
for (int i = 0; i < n; i++)
map.put(i, new HashSet<>());

for (List<Integer> curPrerequisite : prerequisites) {
}

return map;
}

private static void processIndependentCourses(Queue<Integer> queue, Map<Integer, Set<Integer>> graph) {

List<Integer> independentCourses = graph.keySet().stream().filter(key -> graph.get(key).isEmpty()).collect(Collectors.toList());
independentCourses.forEach(key -> graph.remove(key));
}

public static List<String> splitWords(String s) {
return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
int prerequisitesLength = Integer.parseInt(scanner.nextLine());
List<List<Integer>> prerequisites = new ArrayList<>();
for (int i = 0; i < prerequisitesLength; i++) {
}
scanner.close();
boolean res = isValidCourseSchedule(n, prerequisites);
System.out.println(res);
}
``````

}

My BFS solution is quite simple. I count the number of visited nodes knowing that if there is a cycle, there will come a time when it will be impossible to add one of the remaining nodes to the queue. As a result, the number of visited nodes at the exit of the loop will be less than the total number of nodes.
bool is_valid_course_schedule(int n, std::vector<std::vector> prerequisites) {
std::vector<std::vector> graph(n, std::vector());
std::vector counts(n, 0);

``````    for (const auto& pr : prerequisites) {
graph[pr[0]].push_back(pr[1]);
++counts[pr[1]];
}

std::queue<int> q;
int used = 0;
for (int i = 0; i < n; ++i) {
if (!counts[i]) {
q.push(i);
++used;
}
}

while (q.size()) {
int node = q.front();
for (const int next : graph[node]) {
--counts[next];
if (!counts[next]) {
q.push(next);
++used;
}
}
q.pop();
}

return used == n;
}
``````

BFS

``````from collections import defaultdict, deque

def is_valid_course_schedule(n: int, prerequisites: List[List[int]]) -> bool:
graph = {course: set() for course in range(n)}
course_to_indegree = defaultdict(int)
for course, prerequiste in prerequisites:
course_to_indegree[course] += 1
queue = deque([course for course in range(n) if course_to_indegree[course] == 0])
visited = set()
while queue:
course = queue.popleft()
for child in graph[course]:
indegree = course_to_indegree[child] - 1
course_to_indegree[child] = indegree
if indegree == 0:
queue.append(child)
return len(visited) == n
``````

DFS

``````def is_valid_course_schedule(n: int, prerequisites: List[List[int]]) -> bool:
graph = {course: set() for course in range(n)}
for course, prerequiste in prerequisites:
visiting = set()
visited = set()
def dfs(node):
for child in graph[node]:
if child in visited:
continue
if child in visiting:
return False
if not dfs(child):
return False