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) {
graph.get(prereq[1]).add(prereq[0]);
}
Map<Integer, Integer> prereqCounts = getPrereqCounts(graph);
Deque<Integer> parents = new ArrayDeque<>();
for (Integer node : prereqCounts.keySet()) {
if (prereqCounts.get(node) == 0)
parents.addLast(node);
}
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)
parents.addLast(course);
}
}
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)
for task, count in counts.items():
if count == 0:
queue.append(task)
while queue:
task = queue.popleft()
result.append(task)
for child in graph[task]:
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))
return top_sort(graph)
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.LinkedList;
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<>();
List<Integer> topologicalSort = new LinkedList<>();
processIndependentCourses(queue, graph);
while (!queue.isEmpty()) {
int curCourse = queue.remove();
topologicalSort.add(curCourse);
for (Integer curKey : graph.keySet()) {
graph.get(curKey).remove(curCourse);
}
processIndependentCourses(queue, graph);
}
return topologicalSort.size() == n;
}
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) {
map.get(curPrerequisite.get(0)).add(curPrerequisite.get(1));
}
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());
queue.addAll(independentCourses);
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++) {
prerequisites.add(splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList()));
}
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.LinkedList;
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<>();
List<Integer> topologicalSort = new LinkedList<>();
processIndependentCourses(queue, graph);
while (!queue.isEmpty()) {
int curCourse = queue.remove();
topologicalSort.add(curCourse);
for (Integer curKey : graph.keySet()) {
graph.get(curKey).remove(curCourse);
}
processIndependentCourses(queue, graph);
}
return topologicalSort.size() == n;
}
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) {
map.get(curPrerequisite.get(0)).add(curPrerequisite.get(1));
}
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());
queue.addAll(independentCourses);
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++) {
prerequisites.add(splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList()));
}
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:
graph[prerequiste].add(course)
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()
visited.add(course)
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:
graph[prerequiste].add(course)
visiting = set()
visited = set()
def dfs(node):
visiting.add(node)
for child in graph[node]:
if child in visited:
continue
if child in visiting:
return False
if not dfs(child):
return False
visited.add(node)
return True
for course in range(n):
if not dfs(course):
return False
return True