# Java Topological Sort with BFS

• Topological sort using BFS by building graph, indegrees count for each node, and set of classes taken.

``````public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> indegrees = new HashMap<>();
Set<Integer> taken = new HashSet<Integer>();

// initialize indegrees and graph
for (int i = 0; i < numCourses; i++) {
indegrees.put(i, 0);
graph.put(i, new HashSet<Integer>());
}

// create edges on graph and indegrees count for each node
for (int i = 0; i < prerequisites.length; i++) {
int clazz = prerequisites[i][0];
int prereq = prerequisites[i][1];

indegrees.put(clazz, indegrees.get(clazz) + 1);
}

// mark every node with 0 indegrees as taken until no more nodes with 0 indegrees
boolean hasNextRoot = true;
while (hasNextRoot) {
hasNextRoot = false;
Set<Integer> indegreesKeys = indegrees.keySet();
for (Integer key : indegreesKeys) {
int indegree = indegrees.get(key);
if (indegree == 0) {
hasNextRoot = true;

// reduce indegree count for all adjacent nodes
Set<Integer> adj = graph.getOrDefault(key, new HashSet<>());
for (Integer dep : adj) {
indegrees.put(dep, indegrees.get(dep) - 1);
}

indegrees.put(key, -1);
}
}
}

// if there is a cycle, not every course will be taken
return taken.size() == numCourses;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.